# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
923059 |
2024-02-06T13:52:19 Z |
pcc |
RMQ (NOI17_rmq) |
C++14 |
|
172 ms |
23376 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const ll mxn = 1e5+10;
const ll inf = 1e10+10;
vector<pii> op[mxn];
ll arr[mxn];
ll N,Q;
struct SEG{
pll seg[mxn*4];
SEG(){
for(auto &i:seg)i.fs = i.sc = 0;
}
void modify(int now,int l,int r,int s,int e,ll v){
if(l>=s&&e>=r){
seg[now].sc += v;
return;
}
int mid = (l+r)>>1;
if(mid>=s)modify(now*2+1,l,mid,s,e,v);
if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
seg[now].fs = max(seg[now*2+1].fs+seg[now*2+1].sc,seg[now*2+2].fs+seg[now*2+2].sc);
return;
}
ll getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now].fs+seg[now].sc;
int mid = (l+r)>>1;
if(mid>=e)return getval(now*2+1,l,mid,s,e)+seg[now].sc;
else if(mid<s)return getval(now*2+2,mid+1,r,s,e)+seg[now].sc;
else return max(getval(now*2+1,l,mid,s,e),getval(now*2+2,mid+1,r,s,e))+seg[now].sc;
}
int getbig(int now,int l,int r){
if(l == r)return l;
int mid = (l+r)>>1;
if(seg[now*2+1].fs+seg[now*2+1].sc<seg[now*2+2].fs+seg[now*2+2].sc)return getbig(now*2+2,mid+1,r);
else return getbig(now*2+1,l,mid);
}
};
SEG seg1,seg2;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>Q;
for(int i = 1;i<=Q;i++){
int s,e,v;
cin>>s>>e>>v;
op[v].push_back({s,e});
seg1.modify(0,0,N-1,s,e,-1);
}
for(int i = 0;i<N;i++){
for(auto &j:op[i])seg1.modify(0,0,N-1,j.fs,j.sc,mxn*mxn+1);
ll p = seg1.getbig(0,0,N-1);
arr[p] = i;
for(auto &j:op[i])seg1.modify(0,0,N-1,j.fs,j.sc,-mxn*mxn);
seg1.modify(0,0,N-1,p,p,-mxn*mxn*mxn);
}
set<int> st;
for(int i = 0;i<N;i++)st.insert(arr[i]),seg2.modify(0,0,N-1,i,i,-arr[i]);
bool flag = true;
if(st.size() != N||*st.begin() != 0||*st.rbegin() != N-1)flag = false;
for(int i = 0;i<N;i++){
for(auto &j:op[i]){
if(seg2.getval(0,0,N-1,j.fs,j.sc) != -i)flag = false;
}
}
if(!flag)for(int i = 0;i<N;i++)cout<<-1<<' ';
else for(int i = 0;i<N;i++)cout<<arr[i]<<' ';
cout<<'\n';
return 0;
}
Compilation message
rmq.cpp: In function 'int main()':
rmq.cpp:69:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
69 | if(st.size() != N||*st.begin() != 0||*st.rbegin() != N-1)flag = false;
| ~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15604 KB |
Output is correct |
2 |
Correct |
7 ms |
15192 KB |
Output is correct |
3 |
Correct |
7 ms |
15196 KB |
Output is correct |
4 |
Correct |
7 ms |
15196 KB |
Output is correct |
5 |
Correct |
6 ms |
15196 KB |
Output is correct |
6 |
Correct |
6 ms |
15196 KB |
Output is correct |
7 |
Correct |
7 ms |
15196 KB |
Output is correct |
8 |
Correct |
6 ms |
15196 KB |
Output is correct |
9 |
Correct |
6 ms |
15196 KB |
Output is correct |
10 |
Correct |
6 ms |
15332 KB |
Output is correct |
11 |
Correct |
8 ms |
15196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15604 KB |
Output is correct |
2 |
Correct |
7 ms |
15192 KB |
Output is correct |
3 |
Correct |
7 ms |
15196 KB |
Output is correct |
4 |
Correct |
7 ms |
15196 KB |
Output is correct |
5 |
Correct |
6 ms |
15196 KB |
Output is correct |
6 |
Correct |
6 ms |
15196 KB |
Output is correct |
7 |
Correct |
7 ms |
15196 KB |
Output is correct |
8 |
Correct |
6 ms |
15196 KB |
Output is correct |
9 |
Correct |
6 ms |
15196 KB |
Output is correct |
10 |
Correct |
6 ms |
15332 KB |
Output is correct |
11 |
Correct |
8 ms |
15196 KB |
Output is correct |
12 |
Correct |
7 ms |
15192 KB |
Output is correct |
13 |
Correct |
9 ms |
15192 KB |
Output is correct |
14 |
Correct |
7 ms |
15192 KB |
Output is correct |
15 |
Correct |
7 ms |
15196 KB |
Output is correct |
16 |
Correct |
8 ms |
15196 KB |
Output is correct |
17 |
Correct |
8 ms |
15196 KB |
Output is correct |
18 |
Correct |
9 ms |
15196 KB |
Output is correct |
19 |
Correct |
7 ms |
15196 KB |
Output is correct |
20 |
Correct |
7 ms |
15192 KB |
Output is correct |
21 |
Correct |
7 ms |
15196 KB |
Output is correct |
22 |
Correct |
7 ms |
15372 KB |
Output is correct |
23 |
Correct |
7 ms |
15196 KB |
Output is correct |
24 |
Correct |
8 ms |
15192 KB |
Output is correct |
25 |
Correct |
7 ms |
15196 KB |
Output is correct |
26 |
Correct |
7 ms |
15196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15604 KB |
Output is correct |
2 |
Correct |
7 ms |
15192 KB |
Output is correct |
3 |
Correct |
7 ms |
15196 KB |
Output is correct |
4 |
Correct |
7 ms |
15196 KB |
Output is correct |
5 |
Correct |
6 ms |
15196 KB |
Output is correct |
6 |
Correct |
6 ms |
15196 KB |
Output is correct |
7 |
Correct |
7 ms |
15196 KB |
Output is correct |
8 |
Correct |
6 ms |
15196 KB |
Output is correct |
9 |
Correct |
6 ms |
15196 KB |
Output is correct |
10 |
Correct |
6 ms |
15332 KB |
Output is correct |
11 |
Correct |
8 ms |
15196 KB |
Output is correct |
12 |
Correct |
7 ms |
15192 KB |
Output is correct |
13 |
Correct |
9 ms |
15192 KB |
Output is correct |
14 |
Correct |
7 ms |
15192 KB |
Output is correct |
15 |
Correct |
7 ms |
15196 KB |
Output is correct |
16 |
Correct |
8 ms |
15196 KB |
Output is correct |
17 |
Correct |
8 ms |
15196 KB |
Output is correct |
18 |
Correct |
9 ms |
15196 KB |
Output is correct |
19 |
Correct |
7 ms |
15196 KB |
Output is correct |
20 |
Correct |
7 ms |
15192 KB |
Output is correct |
21 |
Correct |
7 ms |
15196 KB |
Output is correct |
22 |
Correct |
7 ms |
15372 KB |
Output is correct |
23 |
Correct |
7 ms |
15196 KB |
Output is correct |
24 |
Correct |
8 ms |
15192 KB |
Output is correct |
25 |
Correct |
7 ms |
15196 KB |
Output is correct |
26 |
Correct |
7 ms |
15196 KB |
Output is correct |
27 |
Correct |
172 ms |
21544 KB |
Output is correct |
28 |
Correct |
142 ms |
21900 KB |
Output is correct |
29 |
Correct |
118 ms |
21260 KB |
Output is correct |
30 |
Correct |
155 ms |
22160 KB |
Output is correct |
31 |
Correct |
133 ms |
20580 KB |
Output is correct |
32 |
Correct |
141 ms |
20680 KB |
Output is correct |
33 |
Correct |
44 ms |
20052 KB |
Output is correct |
34 |
Correct |
31 ms |
18528 KB |
Output is correct |
35 |
Correct |
58 ms |
21052 KB |
Output is correct |
36 |
Correct |
146 ms |
22960 KB |
Output is correct |
37 |
Correct |
162 ms |
23376 KB |
Output is correct |
38 |
Correct |
36 ms |
19028 KB |
Output is correct |
39 |
Correct |
135 ms |
21620 KB |
Output is correct |
40 |
Correct |
6 ms |
15196 KB |
Output is correct |
41 |
Correct |
7 ms |
15196 KB |
Output is correct |