#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int blk=700;
int n,q;
int x[400005],idx[400005],fl[400005],fr[400005];
priority_queue<int> all[400005],vals[400005];
int ins(int i,int v){
if(all[i].top()<=v) return v;
int ret=all[i].top();
vals[i].push(-v);
all[i].pop();
all[i].push(v);
return ret;
}
void push(int i){
for(int j=fl[i];j<=fr[i];j++){
if(!vals[i].empty()&&x[j]>-vals[i].top()){
vals[i].push(-x[j]);
x[j]=-vals[i].top();
vals[i].pop();
}
}
while(!vals[i].empty()) vals[i].pop();
}
void build(int i){
while(!all[i].empty()) all[i].pop();
for(int j=fl[i];j<=fr[i];j++){
all[i].push(x[j]);
}
}
int update(int l,int r,int v){
if(idx[l]==idx[r]){
push(idx[l]);
for(int i=l;i<=r;i++){
if(v<x[i]) swap(v,x[i]);
}
build(idx[l]);
return v;
}
push(idx[l]);
for(int i=l;i<=fr[idx[l]];i++){
if(v<x[i]) swap(v,x[i]);
}
build(idx[l]);
for(int i=idx[l]+1;i<idx[r];i++){
v=ins(i,v);
}
push(idx[r]);
for(int i=fl[idx[r]];i<=r;i++){
if(v<x[i]) swap(v,x[i]);
}
build(idx[r]);
return v;
}
int main(){
n=readint(); q=readint();
for(int i=1;i<=n;i++) x[i]=readint();
for(int i=0;i<=n;i++) fl[i]=1e9,fr[i]=-1;
for(int i=1;i<=n;i++){
idx[i]=i/blk;
fl[idx[i]]=min(fl[idx[i]],i);
fr[idx[i]]=max(fr[idx[i]],i);
all[idx[i]].push(x[i]);
}
while(q--){
int l=readint(),r=readint(),v=readint();
if(l<=r){
fflush(stdout);
v=update(l,r,v);
}else{
v=update(l,n,v);
v=update(1,r,v);
}
printf("%d\n",v);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
31320 KB |
Output is correct |
2 |
Correct |
194 ms |
31572 KB |
Output is correct |
3 |
Correct |
192 ms |
31320 KB |
Output is correct |
4 |
Correct |
187 ms |
31580 KB |
Output is correct |
5 |
Correct |
211 ms |
31436 KB |
Output is correct |
6 |
Correct |
192 ms |
31320 KB |
Output is correct |
7 |
Correct |
55 ms |
31576 KB |
Output is correct |
8 |
Correct |
65 ms |
31324 KB |
Output is correct |
9 |
Correct |
190 ms |
31472 KB |
Output is correct |
10 |
Correct |
190 ms |
31652 KB |
Output is correct |
11 |
Correct |
186 ms |
31576 KB |
Output is correct |
12 |
Correct |
194 ms |
31456 KB |
Output is correct |
13 |
Correct |
213 ms |
31460 KB |
Output is correct |
14 |
Correct |
274 ms |
31476 KB |
Output is correct |
15 |
Correct |
272 ms |
31456 KB |
Output is correct |
16 |
Correct |
94 ms |
31464 KB |
Output is correct |
17 |
Correct |
7 ms |
31320 KB |
Output is correct |
18 |
Correct |
8 ms |
31332 KB |
Output is correct |
19 |
Correct |
6 ms |
31320 KB |
Output is correct |
20 |
Correct |
6 ms |
31324 KB |
Output is correct |
21 |
Correct |
6 ms |
31324 KB |
Output is correct |
22 |
Correct |
6 ms |
31324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2979 ms |
105152 KB |
Output is correct |
2 |
Correct |
3055 ms |
103660 KB |
Output is correct |
3 |
Correct |
413 ms |
35404 KB |
Output is correct |
4 |
Correct |
2982 ms |
105440 KB |
Output is correct |
5 |
Correct |
2189 ms |
104492 KB |
Output is correct |
6 |
Correct |
3177 ms |
104280 KB |
Output is correct |
7 |
Correct |
3138 ms |
104316 KB |
Output is correct |
8 |
Correct |
3102 ms |
104460 KB |
Output is correct |
9 |
Correct |
373 ms |
35340 KB |
Output is correct |
10 |
Correct |
2108 ms |
99232 KB |
Output is correct |
11 |
Correct |
383 ms |
35052 KB |
Output is correct |
12 |
Correct |
2176 ms |
100400 KB |
Output is correct |
13 |
Correct |
2978 ms |
105148 KB |
Output is correct |
14 |
Correct |
3040 ms |
103908 KB |
Output is correct |
15 |
Correct |
417 ms |
35412 KB |
Output is correct |
16 |
Correct |
2907 ms |
104712 KB |
Output is correct |
17 |
Correct |
2160 ms |
104220 KB |
Output is correct |
18 |
Correct |
3120 ms |
104488 KB |
Output is correct |
19 |
Correct |
3181 ms |
104276 KB |
Output is correct |
20 |
Correct |
3131 ms |
104564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
31320 KB |
Output is correct |
2 |
Correct |
194 ms |
31572 KB |
Output is correct |
3 |
Correct |
192 ms |
31320 KB |
Output is correct |
4 |
Correct |
187 ms |
31580 KB |
Output is correct |
5 |
Correct |
211 ms |
31436 KB |
Output is correct |
6 |
Correct |
192 ms |
31320 KB |
Output is correct |
7 |
Correct |
55 ms |
31576 KB |
Output is correct |
8 |
Correct |
65 ms |
31324 KB |
Output is correct |
9 |
Correct |
190 ms |
31472 KB |
Output is correct |
10 |
Correct |
190 ms |
31652 KB |
Output is correct |
11 |
Correct |
186 ms |
31576 KB |
Output is correct |
12 |
Correct |
194 ms |
31456 KB |
Output is correct |
13 |
Correct |
213 ms |
31460 KB |
Output is correct |
14 |
Correct |
274 ms |
31476 KB |
Output is correct |
15 |
Correct |
272 ms |
31456 KB |
Output is correct |
16 |
Correct |
94 ms |
31464 KB |
Output is correct |
17 |
Correct |
7 ms |
31320 KB |
Output is correct |
18 |
Correct |
8 ms |
31332 KB |
Output is correct |
19 |
Correct |
6 ms |
31320 KB |
Output is correct |
20 |
Correct |
6 ms |
31324 KB |
Output is correct |
21 |
Correct |
6 ms |
31324 KB |
Output is correct |
22 |
Correct |
6 ms |
31324 KB |
Output is correct |
23 |
Correct |
2979 ms |
105152 KB |
Output is correct |
24 |
Correct |
3055 ms |
103660 KB |
Output is correct |
25 |
Correct |
413 ms |
35404 KB |
Output is correct |
26 |
Correct |
2982 ms |
105440 KB |
Output is correct |
27 |
Correct |
2189 ms |
104492 KB |
Output is correct |
28 |
Correct |
3177 ms |
104280 KB |
Output is correct |
29 |
Correct |
3138 ms |
104316 KB |
Output is correct |
30 |
Correct |
3102 ms |
104460 KB |
Output is correct |
31 |
Correct |
373 ms |
35340 KB |
Output is correct |
32 |
Correct |
2108 ms |
99232 KB |
Output is correct |
33 |
Correct |
383 ms |
35052 KB |
Output is correct |
34 |
Correct |
2176 ms |
100400 KB |
Output is correct |
35 |
Correct |
2978 ms |
105148 KB |
Output is correct |
36 |
Correct |
3040 ms |
103908 KB |
Output is correct |
37 |
Correct |
417 ms |
35412 KB |
Output is correct |
38 |
Correct |
2907 ms |
104712 KB |
Output is correct |
39 |
Correct |
2160 ms |
104220 KB |
Output is correct |
40 |
Correct |
3120 ms |
104488 KB |
Output is correct |
41 |
Correct |
3181 ms |
104276 KB |
Output is correct |
42 |
Correct |
3131 ms |
104564 KB |
Output is correct |
43 |
Correct |
3123 ms |
39160 KB |
Output is correct |
44 |
Correct |
3105 ms |
39136 KB |
Output is correct |
45 |
Correct |
1394 ms |
35704 KB |
Output is correct |
46 |
Correct |
3075 ms |
39800 KB |
Output is correct |
47 |
Correct |
3086 ms |
39532 KB |
Output is correct |
48 |
Correct |
4384 ms |
41140 KB |
Output is correct |
49 |
Correct |
4826 ms |
40636 KB |
Output is correct |
50 |
Correct |
4796 ms |
40836 KB |
Output is correct |
51 |
Correct |
4998 ms |
40756 KB |
Output is correct |
52 |
Correct |
3885 ms |
40060 KB |
Output is correct |
53 |
Correct |
3711 ms |
39968 KB |
Output is correct |
54 |
Correct |
4916 ms |
42728 KB |
Output is correct |
55 |
Correct |
5311 ms |
42948 KB |
Output is correct |
56 |
Correct |
5335 ms |
42932 KB |
Output is correct |
57 |
Correct |
5208 ms |
42852 KB |
Output is correct |
58 |
Correct |
3722 ms |
43052 KB |
Output is correct |
59 |
Correct |
3014 ms |
43096 KB |
Output is correct |
60 |
Correct |
2478 ms |
104324 KB |
Output is correct |
61 |
Correct |
3078 ms |
104140 KB |
Output is correct |
62 |
Correct |
3108 ms |
104608 KB |
Output is correct |
63 |
Correct |
3006 ms |
104208 KB |
Output is correct |
64 |
Correct |
766 ms |
35444 KB |
Output is correct |
65 |
Correct |
1843 ms |
69128 KB |
Output is correct |
66 |
Correct |
1841 ms |
69796 KB |
Output is correct |
67 |
Correct |
3757 ms |
74644 KB |
Output is correct |
68 |
Correct |
4526 ms |
74488 KB |
Output is correct |
69 |
Correct |
4533 ms |
74424 KB |
Output is correct |
70 |
Correct |
4537 ms |
74420 KB |
Output is correct |