Submission #1173574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173574		PenguinsAreCute	Curtains (NOI23_curtains)	C++17	100 / 100	929 ms	266348 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500069
#define LOGN 20
#define orzpayment(x) 1210
int stuff[LOGN][MAXN];
int seg[LOGN][MAXN<<1];
bool self[MAXN];
vector<int> ranges[MAXN];
void init(int idx) {
	for(int i=1;i<(MAXN<<1);i++) seg[idx][i]=12102010;
}
void up(int idx, int x, int v) {
	for(seg[idx][x+=MAXN]=v;x>1;x>>=1) seg[idx][x>>1]=min(seg[idx][x],seg[idx][x^1]);
}
int qry(int idx, int l, int r) {
	int ans = 12102010;
	for(l+=MAXN,r+=MAXN;l<r;l>>=1,r>>=1) {
		if(l&1) ans=min(ans,seg[idx][l++]);
		if(r&1) ans=min(ans,seg[idx][--r]);
	}
	return ans;
}
void dnc(int h, int l, int r) { // [l,r)
	int m = l + r >> 1;
	for(int i=m;i<r;i++) {
		stuff[h][i] = -12102010;
		for(auto j: ranges[i]) {
			if(j>i) continue;
			if(j<=m) stuff[h][i]=max(stuff[h][i],j);
			else stuff[h][i]=max(stuff[h][i],-qry(h,j-1,i));
		}
		up(h,i,-stuff[h][i]);
		orzpayment(l); orzpayment(r); orzpayment(m); orzpayment(h); orzpayment(i); orzpayment(stuff[h][i]);
	}
	for(int i=m-1;i>=l;i--) {
		stuff[h][i]=12102010;
		for(auto j: ranges[i]) {
			if(j<i) continue;
			if(j>=m-1) stuff[h][i]=min(stuff[h][i],j);
			else stuff[h][i]=min(stuff[h][i],qry(h,i+1,j+2));
		}
		up(h,i,stuff[h][i]);
		orzpayment(l); orzpayment(r); orzpayment(m); orzpayment(h); orzpayment(i); orzpayment(stuff[h][i]);
	}
	if(r-l>1) {
		dnc(h+1,l,m);
		dnc(h+1,m,r);
	}
}
bool qry(int ql, int qr, int h, int l, int r) {
	int m = l+r>>1;
	if(qr>=m && ql<m) return (stuff[h][ql]<=qr && stuff[h][qr]>=ql);
	else if(qr<m) return qry(ql,qr,h+1,l,m);
	else return qry(ql,qr,h+1,m,r);
}
main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, q; cin >> n >> m >> q;
	for(int l,r;m--;) {
		cin >> l >> r;
		ranges[l].push_back(r);
		ranges[r].push_back(l);
		if(l==r) self[l]=1;
	}
	for(int i=0;i<LOGN;i++) init(i);
	dnc(0,1,n+1);
	for(int l,r;q--;) {
		cin >> l >> r;
		if(l==r) cout<<(self[l]?"YES\n":"NO\n");
		else cout<<(qry(l,r,0,1,n+1)?"YES\n":"NO\n");
	}
}

Compilation message (stderr)

curtains.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main() {
      | ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20