Submission #955905

#TimeUsernameProblemLanguageResultExecution timeMemory
955905AlphaMale06Curtains (NOI23_curtains)C++14
0 / 100
13 ms31324 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define yes cout << "YES\n" #define no cout << "NO\n" #define F first #define S second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define int long long struct query{ int l, r, ind; string ans; }; const int N = 5e5+3; pair<int, int> lr[N]; int st[4*N], lz[4*N]; query qs[N]; void push(int v){ int lc = 2*v+1; int rc = 2*v+2; st[lc]=max(st[lc], lz[v]); st[rc]=max(st[rc], lz[v]); lz[lc]=max(lz[lc], lz[v]); lz[rc]=max(lz[rc], lz[v]); } void Update(int v, int l, int r, int L, int R, int val){ if(l>r || l>R || r<L)return; if(l>=L && r<=R){ st[v]=max(st[v], val); lz[v]=max(lz[v], val); return; } push(v); int mid = l+r>>1; Update(2*v+1, l, mid, L, R, val); Update(2*v+2, mid+1, r, L, R, val); st[v]=min(st[2*v+1], st[2*v+2]); } int Get(int v, int l, int r, int L, int R){ if(l>r || l>R || r<L)return 1e9; if(l>=L && r<=R)return st[v]; push(v); int mid = l+r>>1; return min(Get(2*v+1, l, mid, L, R), Get(2*v+2, mid+1, r, L, R)); } bool cmp1(query A, query B){ return A.r<B.r; } bool cmp2(query A, query B){ return A.ind < B.ind; } void solve(){ int n, m, q; cin >> n >> m >> q; for(int i=0; i< m; i++){ cin >> lr[i].S >> lr[i].F; } sort(lr, lr+m); for(int i=0; i< m; i++){ swap(lr[i].F, lr[i].S); } for(int i=0; i< q; i++){ cin >> qs[i].l >> qs[i].r; qs[i].ind=i; } sort(qs, qs+q, cmp1); int p=0; for(int i=0; i< q; i++){ while(p<m && lr[p].S<=qs[i].r){ Update(0, 1, n, lr[i].F, lr[i].S, lr[i].F); p++; } if(Get(0, 1, n, qs[i].l, qs[i].r)>=qs[i].l)qs[i].ans="YES"; else qs[i].ans="NO"; } sort(qs, qs+q, cmp2); for(int i=0; i< q; i++){ cout << qs[i].ans << '\n'; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); solve(); }

Compilation message (stderr)

curtains.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  int mid = l+r>>1;
      |            ~^~
curtains.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid = l+r>>1;
      |            ~^~
#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...