| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 294530 |
2020-09-09T04:04:07 Z |
nandonathaniel |
RMQ (NOI17_rmq) |
C++14 |
|
218 ms |
9068 KB |
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int MAXN=100005;
int a[MAXN],n,lazy[4*MAXN];
bool udah[MAXN],udhidx[MAXN];
pii segment[MAXN],tree[4*MAXN];
void updatenode(int now,int val){
tree[now].first+=val;
lazy[now]+=val;
}
void ganti1(int pos,int val){
tree[pos].first=max(tree[pos].first,val);
}
void build(int now,int L,int R){
if(L==R){
tree[now]={a[L],L};
return;
}
int mid=(L+R)/2;
build(2*now,L,mid);
build(2*now+1,mid+1,R);
tree[now]=min(tree[2*now],tree[2*now+1]);
}
void pushdown(int now){
updatenode(2*now,lazy[now]);
updatenode(2*now+1,lazy[now]);
lazy[now]=0;
ganti1(2*now,tree[now].first);
ganti1(2*now+1,tree[now].first);
}
void update(int now,int L,int R,int x,int y,int val){
if(L>=x && R<=y){
ganti1(now,val);
return;
}
if(L>y || R<x)return;
pushdown(now);
int mid=(L+R)/2;
update(2*now,L,mid,x,y,val);
update(2*now+1,mid+1,R,x,y,val);
tree[now]=min(tree[2*now],tree[2*now+1]);
}
pii query(int now,int L,int R,int x,int y){
if(L>=x && R<=y)return tree[now];
if(L>y || R<x)return {1e9,1e9};
pushdown(now);
int mid=(L+R)/2;
return min(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}
void gagal(){
for(int i=1;i<=n;i++){
cout << -1;
if(i<n)cout << " ";
else cout << '\n';
}
exit(0);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int q,u,v,w;
cin >> n >> q;
vector<piii> que;
for(int i=1;i<=q;i++){
cin >> u >> v >> w;
u++;v++;w++;
que.push_back({w,{u,v}});
}
for(int i=1;i<=n;i++){
a[i]=-1;
segment[i].first=-1;
segment[i].second=-1;
}
build(1,1,n);
sort(que.begin(),que.end());
reverse(que.begin(),que.end());
for(auto isi : que){
//for(int i=1;i<=n;i++)cout << query(1,1,n,i,i).first << " ";
//cout << '\n';
if(segment[isi.first].first==-1){
segment[isi.first].first=isi.second.first;
segment[isi.first].second=isi.second.second;
}
else{
if(segment[isi.first].second<isi.second.first){
gagal();
}
else if(isi.second.second<segment[isi.first].first){
gagal();
}
segment[isi.first].first=max(segment[isi.first].first,isi.second.first);
segment[isi.first].second=min(segment[isi.first].second,isi.second.second);
}
int x=isi.second.first,y=isi.second.second;
pii tanya=query(1,1,n,isi.second.first,isi.second.second);
if(tanya.first==-1 || tanya.first==isi.first){
update(1,1,n,isi.second.first,isi.second.second,isi.first);
}
else{
gagal();
}
}
vector<pii> V;
for(int i=1;i<=n;i++){
if(segment[i].first==-1)continue;
pii tanya=query(1,1,n,segment[i].first,segment[i].second);
if(tanya.first==i){
udah[i]=true;
udhidx[tanya.second]=true;
}
else gagal();
}
for(int i=1;i<=n;i++)a[i]=query(1,1,n,i,i).first;
for(int i=1;i<=n;i++){
if(udhidx[i])continue;
V.push_back({a[i],i});
}
sort(V.begin(),V.end());
reverse(V.begin(),V.end());
int now=n;
for(auto isi : V){
while(now>=1 && udah[now])now--;
if(now==0)gagal();
if(isi.first>now)gagal();
a[isi.second]=now;
udah[now]=true;
}
for(int i=1;i<=n;i++){
cout << a[i]-1;
if(i<n)cout << " ";
else cout << '\n';
}
return 0;
}
Compilation message
rmq.cpp: In function 'int main()':
rmq.cpp:103:7: warning: unused variable 'x' [-Wunused-variable]
103 | int x=isi.second.first,y=isi.second.second;
| ^
rmq.cpp:103:26: warning: unused variable 'y' [-Wunused-variable]
103 | int x=isi.second.first,y=isi.second.second;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
2 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
2 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
0 ms |
384 KB |
Output is correct |
| 27 |
Correct |
209 ms |
8940 KB |
Output is correct |
| 28 |
Correct |
190 ms |
8684 KB |
Output is correct |
| 29 |
Correct |
159 ms |
7664 KB |
Output is correct |
| 30 |
Correct |
218 ms |
9068 KB |
Output is correct |
| 31 |
Correct |
161 ms |
5996 KB |
Output is correct |
| 32 |
Correct |
187 ms |
6252 KB |
Output is correct |
| 33 |
Correct |
44 ms |
5744 KB |
Output is correct |
| 34 |
Correct |
30 ms |
3580 KB |
Output is correct |
| 35 |
Correct |
70 ms |
6504 KB |
Output is correct |
| 36 |
Correct |
29 ms |
5624 KB |
Output is correct |
| 37 |
Correct |
40 ms |
6244 KB |
Output is correct |
| 38 |
Correct |
8 ms |
3584 KB |
Output is correct |
| 39 |
Correct |
38 ms |
5736 KB |
Output is correct |
| 40 |
Correct |
1 ms |
384 KB |
Output is correct |
| 41 |
Correct |
0 ms |
384 KB |
Output is correct |
