oj.uz

Submission #865966

# Submission time Handle Problem Language Result Execution time Memory
865966 2023-10-25T07:13:22 Z phoenix0423 Examination (JOI19_examination) C++17
20 / 100
 1473 ms 555664 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const int INF = 1e9;
int n, Q;
int ans[maxn];

struct info{
	int x, y, ttl, id;
	info(int _a, int _b, int _ttl, int _id = 0) : x(_a), y(_b), ttl(_ttl), id(_id){}
	bool operator < (const info& other) const{
		return ttl < other.ttl;
	}
};

vector<int> val, val2;
int getid(int x){
	return lower_bound(val.begin(), val.end(), x) - val.begin();
}
int getid2(int x){
	return lower_bound(val2.begin(), val2.end(), x) - val2.begin();
}

struct SGT{
	struct node{
		int val;
		node *l, *r;
		node() : val(0), l(nullptr), r(nullptr){}
	} *rt;
	void init(){rt = new node();}
	void upd(int pos, int val, node *&nd, int l, int r){
		if(!nd) nd = new node();
		nd->val += val;
		if(l == r) return;
		int m = (l + r) / 2;
		if(pos <= m) upd(pos, val, nd->l, l, m);
		else upd(pos, val, nd->r, m + 1, r);
	}
	void upd(int pos, int val){ upd(pos, val, rt, 0, maxn - 1);}
	int qry(int l, int r, node *nd, int L, int R){
		if(!nd) return 0;
		if(l > R || r < L) return 0;
		if(l <= L && r >= R) return nd->val;
		int m = (L + R) / 2;
		return qry(l, r, nd->l, L, m) + qry(l, r, nd->r, m + 1, R);
	}
	int qry(int l, int r){ return qry(l, r, rt, 0, maxn - 1);}
} BIT[maxn];

void upd(int x, int y, int val){
	x++, y++;
	while(x < maxn){
		BIT[x].upd(y, val);
		x += lowbit(x);
	}
}

int qry(int x, int y){
	x++, y++;
	int ret = 0;
	while(x > 0){
		ret += BIT[x].qry(0, y);
		x -= lowbit(x);
	}
	return ret;
}

int main(void){
	fastio;
	cin>>n>>Q;
	vector<info> a, q;
	for(int i = 0; i < n; i++){
		int x, y;
		cin>>x>>y;
		val.pb(x), val2.pb(y);
		a.pb(info(x, y, x + y));
	}
	for(int i = 0; i < Q; i++){
		int x, y, z;
		cin>>x>>y>>z;
		val.pb(x), val2.pb(y);
		q.pb(info(x, y, z, i));
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
	sort(val2.begin(), val2.end());
	val2.erase(unique(val2.begin(), val2.end()), val2.end());
	sort(a.begin(), a.end());
	sort(q.begin(), q.end());
	for(int i = 0; i < maxn; i++) BIT[i].init();
	for(int i = 0; i < n; i++){
		a[i].x = getid(a[i].x), a[i].y = getid2(a[i].y);
		upd(a[i].x, a[i].y, 1);
	}
	int pos = 0;
	for(int i = 0; i < Q; i++){
		auto [x, y, z, id] = q[i];
		while(a[pos].ttl < z) upd(a[pos].x, a[pos].y, -1), pos++;
		if(pos == n) break;
		x = getid(x), y = getid2(y);
		ans[id] = n - pos - qry(x - 1, maxn - 1) - qry(maxn - 1, y - 1) + qry(x - 1, y - 1);
	}
	for(int i = 0; i < Q; i++) cout<<ans[i]<<"\n";
	cout<<"\n";

}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8792 KB Output is correct
2 Correct 6 ms 8792 KB Output is correct
3 Correct 6 ms 8960 KB Output is correct
4 Incorrect 6 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 276240 KB Output is correct
2 Correct 1008 ms 276068 KB Output is correct
3 Correct 997 ms 275864 KB Output is correct
4 Correct 325 ms 68028 KB Output is correct
5 Correct 311 ms 103960 KB Output is correct
6 Correct 134 ms 15260 KB Output is correct
7 Correct 720 ms 265224 KB Output is correct
8 Correct 748 ms 266512 KB Output is correct
9 Correct 645 ms 256952 KB Output is correct
10 Correct 258 ms 98676 KB Output is correct
11 Correct 269 ms 57276 KB Output is correct
12 Correct 113 ms 15036 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 276240 KB Output is correct
2 Correct 1008 ms 276068 KB Output is correct
3 Correct 997 ms 275864 KB Output is correct
4 Correct 325 ms 68028 KB Output is correct
5 Correct 311 ms 103960 KB Output is correct
6 Correct 134 ms 15260 KB Output is correct
7 Correct 720 ms 265224 KB Output is correct
8 Correct 748 ms 266512 KB Output is correct
9 Correct 645 ms 256952 KB Output is correct
10 Correct 258 ms 98676 KB Output is correct
11 Correct 269 ms 57276 KB Output is correct
12 Correct 113 ms 15036 KB Output is correct
13 Runtime error 1473 ms 555664 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8792 KB Output is correct
2 Correct 6 ms 8792 KB Output is correct
3 Correct 6 ms 8960 KB Output is correct
4 Incorrect 6 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -