| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55385 |
2018-07-07T06:22:32 Z |
노영훈(#1544) |
Employment (JOI16_employment) |
C++11 |
|
376 ms |
9904 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9, XMX=400010;
int n, q;
int A[MX];
struct query{
int type, x, y;
void scan(){
cin>>type>>x;
if(type==2) cin>>y;
}
} Q[MX];
vector<int> X;
int find(int x){
return lower_bound(X.begin(), X.end(), x)-X.begin()+1;
}
int lim;
struct BIT {
int tree[XMX], n;
void init(int sz){
n=sz;
for(int i=1; i<=n; i++) tree[i]=0;
}
void upt(int pos, int val){
if(val==0) return;
for(; 0<pos && pos<=n; pos+=pos&(-pos))
tree[pos]+=val;
}
int sum(int x){
int res=0;
for(; 0<x; x-=x&(-x)) res+=tree[x];
return res;
}
int sum(int l, int r){
return sum(r)-sum(l-1);
}
} Vtree, Etree;
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>q;
for(int i=1; i<=n; i++){
cin>>A[i];
X.push_back(A[i]);
}
for(int i=1; i<=q; i++){
Q[i].scan();
if(Q[i].type==2)
X.push_back(Q[i].y);
else
X.push_back(Q[i].x);
}
sort(X.begin(), X.end());
lim=unique(X.begin(), X.end())-X.begin();
X.resize(lim);
for(int i=1; i<=n; i++) A[i]=find(A[i]);
for(int i=1; i<=q; i++)
if(Q[i].type==2) Q[i].y=find(Q[i].y);
else Q[i].x=find(Q[i].x);
Vtree.init(lim);
Etree.init(lim);
for(int i=1; i<=n; i++) Vtree.upt(A[i], 1);
for(int i=1; i<=n; i++){
if(1<i) Etree.upt(A[i], A[i-1]>A[i]);
if(i<n) Etree.upt(A[i], A[i+1]>=A[i]);
}
for(int idx=1; idx<=q; idx++){
if(Q[idx].type==1){
cout<<Vtree.sum(Q[idx].x, lim) - Etree.sum(Q[idx].x, lim)<<'\n';
}
else{
int i=Q[idx].x, b=Q[idx].y, a=A[i]; // a -> b
A[i]=b;
Vtree.upt(a,-1); Vtree.upt(b,1);
if(1<i) Etree.upt(a, -(A[i-1]>a)), Etree.upt(A[i-1], -(a>=A[i-1]));
if(i<n) Etree.upt(a, -(A[i+1]>=a)), Etree.upt(A[i+1], -(a>A[i+1]));
if(1<i) Etree.upt(b, (A[i-1]>b)), Etree.upt(A[i-1], (b>=A[i-1]));
if(i<n) Etree.upt(b, (A[i+1]>=b)), Etree.upt(A[i+1], (b>A[i+1]));
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
396 KB |
Output is correct |
| 4 |
Correct |
3 ms |
412 KB |
Output is correct |
| 5 |
Correct |
3 ms |
412 KB |
Output is correct |
| 6 |
Correct |
3 ms |
412 KB |
Output is correct |
| 7 |
Correct |
4 ms |
724 KB |
Output is correct |
| 8 |
Correct |
5 ms |
724 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| 10 |
Correct |
4 ms |
724 KB |
Output is correct |
| 11 |
Correct |
5 ms |
744 KB |
Output is correct |
| 12 |
Correct |
4 ms |
744 KB |
Output is correct |
| 13 |
Correct |
4 ms |
748 KB |
Output is correct |
| 14 |
Correct |
4 ms |
748 KB |
Output is correct |
| 15 |
Correct |
4 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
768 KB |
Output is correct |
| 2 |
Correct |
5 ms |
768 KB |
Output is correct |
| 3 |
Correct |
4 ms |
780 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1476 KB |
Output is correct |
| 5 |
Correct |
36 ms |
2092 KB |
Output is correct |
| 6 |
Correct |
65 ms |
3116 KB |
Output is correct |
| 7 |
Correct |
79 ms |
4184 KB |
Output is correct |
| 8 |
Correct |
105 ms |
5080 KB |
Output is correct |
| 9 |
Correct |
175 ms |
8108 KB |
Output is correct |
| 10 |
Correct |
191 ms |
8108 KB |
Output is correct |
| 11 |
Correct |
246 ms |
8876 KB |
Output is correct |
| 12 |
Correct |
294 ms |
9644 KB |
Output is correct |
| 13 |
Correct |
255 ms |
9816 KB |
Output is correct |
| 14 |
Correct |
230 ms |
9816 KB |
Output is correct |
| 15 |
Correct |
252 ms |
9816 KB |
Output is correct |
| 16 |
Correct |
282 ms |
9904 KB |
Output is correct |
| 17 |
Correct |
276 ms |
9904 KB |
Output is correct |
| 18 |
Correct |
278 ms |
9904 KB |
Output is correct |
| 19 |
Correct |
273 ms |
9904 KB |
Output is correct |
| 20 |
Correct |
241 ms |
9904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
396 KB |
Output is correct |
| 4 |
Correct |
3 ms |
412 KB |
Output is correct |
| 5 |
Correct |
3 ms |
412 KB |
Output is correct |
| 6 |
Correct |
3 ms |
412 KB |
Output is correct |
| 7 |
Correct |
4 ms |
724 KB |
Output is correct |
| 8 |
Correct |
5 ms |
724 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| 10 |
Correct |
4 ms |
724 KB |
Output is correct |
| 11 |
Correct |
5 ms |
744 KB |
Output is correct |
| 12 |
Correct |
4 ms |
744 KB |
Output is correct |
| 13 |
Correct |
4 ms |
748 KB |
Output is correct |
| 14 |
Correct |
4 ms |
748 KB |
Output is correct |
| 15 |
Correct |
4 ms |
748 KB |
Output is correct |
| 16 |
Correct |
5 ms |
768 KB |
Output is correct |
| 17 |
Correct |
5 ms |
768 KB |
Output is correct |
| 18 |
Correct |
4 ms |
780 KB |
Output is correct |
| 19 |
Correct |
22 ms |
1476 KB |
Output is correct |
| 20 |
Correct |
36 ms |
2092 KB |
Output is correct |
| 21 |
Correct |
65 ms |
3116 KB |
Output is correct |
| 22 |
Correct |
79 ms |
4184 KB |
Output is correct |
| 23 |
Correct |
105 ms |
5080 KB |
Output is correct |
| 24 |
Correct |
175 ms |
8108 KB |
Output is correct |
| 25 |
Correct |
191 ms |
8108 KB |
Output is correct |
| 26 |
Correct |
246 ms |
8876 KB |
Output is correct |
| 27 |
Correct |
294 ms |
9644 KB |
Output is correct |
| 28 |
Correct |
255 ms |
9816 KB |
Output is correct |
| 29 |
Correct |
230 ms |
9816 KB |
Output is correct |
| 30 |
Correct |
252 ms |
9816 KB |
Output is correct |
| 31 |
Correct |
282 ms |
9904 KB |
Output is correct |
| 32 |
Correct |
276 ms |
9904 KB |
Output is correct |
| 33 |
Correct |
278 ms |
9904 KB |
Output is correct |
| 34 |
Correct |
273 ms |
9904 KB |
Output is correct |
| 35 |
Correct |
241 ms |
9904 KB |
Output is correct |
| 36 |
Correct |
3 ms |
9904 KB |
Output is correct |
| 37 |
Correct |
4 ms |
9904 KB |
Output is correct |
| 38 |
Correct |
4 ms |
9904 KB |
Output is correct |
| 39 |
Correct |
18 ms |
9904 KB |
Output is correct |
| 40 |
Correct |
37 ms |
9904 KB |
Output is correct |
| 41 |
Correct |
64 ms |
9904 KB |
Output is correct |
| 42 |
Correct |
103 ms |
9904 KB |
Output is correct |
| 43 |
Correct |
160 ms |
9904 KB |
Output is correct |
| 44 |
Correct |
303 ms |
9904 KB |
Output is correct |
| 45 |
Correct |
233 ms |
9904 KB |
Output is correct |
| 46 |
Correct |
236 ms |
9904 KB |
Output is correct |
| 47 |
Correct |
319 ms |
9904 KB |
Output is correct |
| 48 |
Correct |
328 ms |
9904 KB |
Output is correct |
| 49 |
Correct |
303 ms |
9904 KB |
Output is correct |
| 50 |
Correct |
376 ms |
9904 KB |
Output is correct |
| 51 |
Correct |
319 ms |
9904 KB |
Output is correct |
| 52 |
Correct |
329 ms |
9904 KB |
Output is correct |
| 53 |
Correct |
338 ms |
9904 KB |
Output is correct |
| 54 |
Correct |
318 ms |
9904 KB |
Output is correct |
| 55 |
Correct |
335 ms |
9904 KB |
Output is correct |
