#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int MAXVAL = 4e5;
const int INF = 2147483647;
struct Data { int t, a, b; };
int N, Q, A[MAXN+10];
Data B[MAXN+10];
int tree[4*MAXVAL+10];
vector<int> comp, comp2;
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }
int getcomp2(int x) { return *lower_bound(comp2.begin(), comp2.end(), x); }
void update(int node, int tl, int tr, int l, int r, int val)
{
if(l>r) return;
if(tr<l || r<tl) return;
if(l<=tl && tr<=r)
{
tree[node]+=val;
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, val);
update(node*2+1, mid+1, tr, l, r, val);
}
int query(int node, int tl, int tr, int pos)
{
if(tl==tr) return tree[node];
int mid=tl+tr>>1;
if(pos<=mid) return tree[node]+query(node*2, tl, mid, pos);
else return tree[node]+query(node*2+1, mid+1, tr, pos);
}
int main()
{
int i, j;
scanf("%d%d", &N, &Q);
for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]), comp.push_back(A[i]+1), comp2.push_back(A[i]);
for(i=1; i<=Q; i++)
{
scanf("%d", &B[i].t);
if(B[i].t==1) scanf("%d", &B[i].a);
else scanf("%d%d", &B[i].a, &B[i].b), comp.push_back(B[i].b), comp.push_back(B[i].b+1), comp2.push_back(B[i].b);
}
comp.push_back(INF); comp.push_back(1); comp2.push_back(INF); comp2.push_back(0);
sort(comp.begin(), comp.end()); sort(comp2.begin(), comp2.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end()); comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());
for(i=1; i<=N+1; i++)
{
int a=min(A[i], A[i-1])+1, b=max(A[i], A[i-1]);
update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
}
for(i=1; i<=Q; i++)
{
if(B[i].t==1) printf("%d\n", query(1, 1, comp.size(), getcomp(getcomp2(B[i].a)))/2);
else
{
int a, b;
a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
update(1, 1, comp.size(), getcomp(a), getcomp(b), -1);
a=min(A[B[i].a], A[B[i].a+1])+1, b=max(A[B[i].a], A[B[i].a+1]);
update(1, 1, comp.size(), getcomp(a), getcomp(b), -1);
A[B[i].a]=B[i].b;
a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
a=min(A[B[i].a], A[B[i].a-1])+1, b=max(A[B[i].a], A[B[i].a-1]);
update(1, 1, comp.size(), getcomp(a), getcomp(b), 1);
}
}
}
Compilation message
employment.cpp: In function 'void update(int, int, int, int, int, int)':
employment.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
employment.cpp: In function 'int query(int, int, int, int)':
employment.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
employment.cpp: In function 'int main()':
employment.cpp:46:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
employment.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
employment.cpp:49:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]), comp.push_back(A[i]+1), comp2.push_back(A[i]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
employment.cpp:52:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &B[i].t);
~~~~~^~~~~~~~~~~~~~~
employment.cpp:53:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if(B[i].t==1) scanf("%d", &B[i].a);
~~~~~^~~~~~~~~~~~~~~
employment.cpp:54:92: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
else scanf("%d%d", &B[i].a, &B[i].b), comp.push_back(B[i].b), comp.push_back(B[i].b+1), comp2.push_back(B[i].b);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
504 KB |
Output is correct |
| 4 |
Correct |
28 ms |
1564 KB |
Output is correct |
| 5 |
Correct |
63 ms |
3312 KB |
Output is correct |
| 6 |
Correct |
89 ms |
4208 KB |
Output is correct |
| 7 |
Correct |
161 ms |
7148 KB |
Output is correct |
| 8 |
Correct |
194 ms |
7916 KB |
Output is correct |
| 9 |
Correct |
332 ms |
11320 KB |
Output is correct |
| 10 |
Correct |
346 ms |
13412 KB |
Output is correct |
| 11 |
Correct |
395 ms |
15208 KB |
Output is correct |
| 12 |
Correct |
457 ms |
16220 KB |
Output is correct |
| 13 |
Correct |
471 ms |
16228 KB |
Output is correct |
| 14 |
Correct |
451 ms |
16104 KB |
Output is correct |
| 15 |
Correct |
463 ms |
16356 KB |
Output is correct |
| 16 |
Correct |
506 ms |
16392 KB |
Output is correct |
| 17 |
Correct |
488 ms |
16400 KB |
Output is correct |
| 18 |
Correct |
494 ms |
16416 KB |
Output is correct |
| 19 |
Correct |
456 ms |
16488 KB |
Output is correct |
| 20 |
Correct |
453 ms |
16564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
