Submission #1102849

#TimeUsernameProblemLanguageResultExecution timeMemory
1102849spycoderytCurtains (NOI23_curtains)C++17
0 / 100
1 ms532 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define f first #define s second using namespace std; const int N = 3e5+5; struct tree{ struct node{ node *l,*r; int sum; node(int k) : sum(k),l(nullptr),r(nullptr) {} node(node* l,node* r) : l(l),r(r) { sum = max((l?l->sum:0),(r?r->sum:0)); } }; public: typedef node* pnode; pnode roots[N]; node* build(int l,int r) { if(l==r)return new node(0); int mid = (l+r)/2; return new node(build(l,mid),build(mid+1,r)); } node* upd(node* cur,int l,int r,int tar,int val) { if(l>r)return 0; if(l==r) return new node(val); assert(cur); int mid = (l+r)/2; if(tar > mid) return new node(cur->l,upd(cur->r,mid+1,r,tar,val)); else return new node(upd(cur->l,l,mid,tar,val),cur->r); } int qry(node*cur,int l,int r,int ll,int rr) { if(!cur)return 0; if(l>r||r<ll|l>rr)return 0; if(l>=ll&&r<=rr)return cur->sum; int mid = (l+r)/2; return max(qry(cur->l,l,mid,ll,rr), qry(cur->r,mid+1,r,ll,rr)); } }t; int n,m,q,a,b; map<int,int> times; int main() { cin>>n>>m>>q; vector<pii> v(m); vector<int> mx(n+1); vector<pii> qv(q); for(int i = 0;i<m;i++) { cin>>v[i].s>>v[i].f; // r, l } for(int i = 0;i<q;i++)cin>>qv[i].f>>qv[i].s; t.roots[0] = t.build(1,n); for(int i = 0;i<m;i++) { times[v[i].f] = i+1; // cout << v[i].f << "awvdwa\n"; mx[v[i].s] = max(mx[v[i].s],v[i].f); t.roots[i+1] = t.upd(t.roots[i],1,n,v[i].s,mx[v[i].s]); } for(int i = 0;i<q;i++) { int can = 1; int time = times[qv[i].s]; if(time ==0){ cout << "NO\n"; continue; } //search from .s to .f, see if max is equal to .f int r = qv[i].s, l = qv[i].s; // cout << l << " " << r << " " << time << "\n"; while(r < qv[i].f) { int oldr = r; r = t.qry(t.roots[time],1,n,l,r); if(oldr <= r) { can = 0; break; } } if(can)cout<<"YES\n"; else cout << "NO\n"; } } /* 6 2 3 1 2 3 4 1 3 1 4 1 5 */

Compilation message (stderr)

curtains.cpp: In constructor 'tree::node::node(int)':
curtains.cpp:10:13: warning: 'tree::node::sum' will be initialized after [-Wreorder]
   10 |         int sum;
      |             ^~~
curtains.cpp:9:15: warning:   'tree::node* tree::node::l' [-Wreorder]
    9 |         node *l,*r;
      |               ^
curtains.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         node(int k) : sum(k),l(nullptr),r(nullptr) {}
      |         ^~~~
curtains.cpp: In member function 'int tree::qry(tree::node*, int, int, int, int)':
curtains.cpp:34:18: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   34 |         if(l>r||r<ll|l>rr)return 0;
      |                 ~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...