Hi!
We all know how important it is to choose a university.
But I have a problem with that.
please help me with choosing a university!
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Hi!
We all know how important it is to choose a university.
But I have a problem with that.
please help me with choosing a university!
how many words per minute you type?
Hello Codeforces!
Today I was solving one problem from codeforces edu
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct segtree {
vector<int> tree;
int size;
const int zero = 0;
void init(int n) {
size = 1;
while (size < n)size *= 2;
tree.assign(size * 2 - 1, 0);
}
void build(vector<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size())
tree[x] = a[lx];
} else {
int mid = (lx + rx) >> 1;
build(a, 2 * x + 1, lx, mid);
build(a, 2 * x + 2, mid, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
}
void build(vector<int> &a) {
init(a.size());
build(a, 0, 0, size);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x] = v;
return;
}
int mid = (lx + rx) >> 1;
if (i < mid)set(i, v, 2 * x + 1, lx, mid);
else set(i, v, 2 * x + 2, mid, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int find(int k, int x, int lx, int rx) {
if (rx - lx == 1) {
return lx;
}
int m = (lx + rx) >> 1;
if (k < tree[2 * x + 1])return find(k, 2 * x + 1, lx, m);
else return find(k - tree[2 * x + 1], 2 * x + 2, m, rx);
}
int find(int k) {
find(k, 0, 0, size);
}
};
int32_t main() {
fast
int n, q;
cin >> n >> q;
vector<int> a(n);
for (auto &i: a)cin >> i;
segtree st;
st.build(a);
while (q--) {
int c;
cin >> c;
if (c == 1) {
int i;
cin >> i;
st.set(i, 1 - a[i]);
a[i] = 1 - a[i];
} else {
int k;
cin >> k;
cout << st.find(k) << endl;
}
}
return 0;
}
/*
* @Nargulyev
*/
Can someone tell me how I can solve this problem? (Sorry for my English)
Thanks!
+ It's my birthday today
Name |
---|