Submission #1189134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189134		nguyn	Curtains (NOI23_curtains)	C++20	100 / 100	616 ms	61184 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 5e5 + 5;

int n, m, q; 
vector<int> vec[N]; 
vector<pii> ev[N]; 
int res[N];
int st[4 * N], lazy[4 * N];

void down(int id) {
	st[id * 2] = max(st[id * 2], lazy[id]);
	st[id * 2 + 1] = max(st[id * 2 + 1], lazy[id]); 
	lazy[id * 2] = max(lazy[id * 2], lazy[id]);
	lazy[id * 2 + 1] = max(lazy[id * 2 + 1], lazy[id]);
}

void update(int id, int l, int r, int u, int v, int x) {
	if (u <= l && r <= v) {
		st[id] = max(x, st[id]); 
		lazy[id] = max(x, lazy[id]);
		return; 
	}
	down(id);
	int mid = (l + r) / 2;
	if (mid >= u) update(id * 2, l, mid, u, v, x);
	if (mid < v) update(id * 2 + 1, mid + 1, r, u, v, x);
	st[id] = min(st[id * 2], st[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v) {
	if (u <= l && r <= v) {
		return st[id];
	}
	down(id); 
	int mid = (l + r) / 2; 
	if (v <= mid) return get(id * 2, l, mid, u, v); 
	if (u > mid) return get(id * 2 + 1, mid + 1, r, u, v);
	return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> m >> q; 
    for (int i = 1; i <= m; i++) {
    	int l, r;
    	cin >> l >> r;
    	vec[r].pb(l);
    }
    for (int i = 1; i <= q; i++) {
    	int l, r;
    	cin >> l >> r;
    	ev[r].pb({l, i});
    }
    for (int i = 1; i <= n; i++) {
    	for (int j : vec[i]) {
    		update(1, 1, n, j, i, j); 
    	}
    	for (pii it : ev[i]) {
    		// cout << get(1, 1, n, it.F, i) << endl;
    		res[it.S] = (get(1, 1, n, it.F, i) >= it.F);
    	}
    }
    for (int i = 1; i <= q; i++) {
    	cout << (res[i] ? "YES\n" : "NO\n");
    }
}

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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