oj.uz

Submission #886092

# Submission time Handle Problem Language Result Execution time Memory
886092 2023-12-11T12:55:05 Z vjudge1 Curtains (NOI23_curtains) C++17
20 / 100
 706 ms 70136 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
//#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define N 500005
#define M 500005
#define L(node) node * 2
#define R(node) node * 2 + 1

const int INF = 1e9 + 7;
int lazy[4 * N];
pii tree[4 * N];

void push(int node, int l, int r){
	tree[node].st += lazy[node];
	if (l != r){
		lazy[L(node)] += lazy[node];
		lazy[R(node)] += lazy[node];
	}
	lazy[node] = 0;
}

pii merge(pii a, pii b){
	if (a.st == b.st) return {a.st, a.nd + b.nd};
	return min(a, b);
}

void update(int node, int l, int r, int sl, int sr, int val){
	push(node, l, r);
	if (l > sr || r < sl) return;
	if (l >= sl && r <= sr){
		lazy[node] += val;
		push(node, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update(L(node), l, mid, sl, sr, val);
	update(R(node), mid + 1, r, sl, sr, val);
	tree[node] = merge(tree[L(node)], tree[R(node)]);
}


void build(int node, int l, int r){
	tree[node] = {0, r - l + 1};
	if (l == r) return;
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
}

pii query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > sr || r < sl) return {INF, 0};
	if (l >= sl && r <= sr) return tree[node];
	int mid = (l + r) / 2;
	return merge(query(L(node), l, mid, sl, sr), query(R(node), mid + 1, r, sl, sr));
}


int32_t main(){
	//fileio();
	fastio();

	int n, m, q;
	cin>>n>>m>>q;
	build(1, 1, n);

	vector<int> l(m + 5, 0), r(m + 5, 0), ans(q + 5, 0);
	vector<vector<int>> ex(n + 5);
	vector<vector<pii>> todo(n + 5);
	for (int i = 1; i <= m; i++){
		cin>>l[i]>>r[i];
		ex[r[i]].pb(l[i]);
	}

	for (int i = 1; i <= q; i++){
		int s, e;
		cin>>s>>e;
		todo[e].pb({s, i});
	}

	for (int i = 1; i <= n; i++){
		for (auto j : ex[i]){
			update(1, 1, n, j, i, 1);
		}
		
		for (auto j : todo[i]){
			if (query(1, 1, n, j.st, i).st != 0) ans[j.nd] = 1;
		}
	}
	
	for (int i = 1; i <= q; i++) {
		if (ans[i]) cout<<"YES\n";
		else cout<<"NO\n";
	}

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 124 ms 10756 KB Output is correct
9 Correct 129 ms 11604 KB Output is correct
10 Correct 296 ms 17656 KB Output is correct
11 Correct 114 ms 10792 KB Output is correct
12 Correct 104 ms 16724 KB Output is correct
13 Correct 104 ms 16724 KB Output is correct
14 Correct 87 ms 16880 KB Output is correct
15 Correct 82 ms 16468 KB Output is correct
16 Correct 88 ms 16720 KB Output is correct
17 Correct 82 ms 16468 KB Output is correct
18 Correct 704 ms 69412 KB Output is correct
19 Correct 706 ms 69992 KB Output is correct
20 Correct 577 ms 70136 KB Output is correct
21 Correct 547 ms 69460 KB Output is correct
22 Correct 543 ms 68436 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -