제출 #923059

#제출 시각아이디문제언어결과실행 시간메모리
923059pccRMQ (NOI17_rmq)C++14
100 / 100
172 ms23376 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...