oj.uz

Submission #666799

# Submission time Handle Problem Language Result Execution time Memory
666799 2022-11-29T18:12:48 Z Koful123 Examination (JOI19_examination) C++17
0 / 100
 3000 ms 38804 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ms multiset<pair<int,int>>
 
struct node{
	multiset<pair<int,int>> s;
};

node merge(node a,node b){
	node res; ms tmp = a.s;
	for(auto[x,y] : b.s){
 		if(x == 0) continue;
 		tmp.insert({x,y});
	}
	int cur = 0;
	for(auto[x,y] : tmp){
		res.s.insert({x,cur}); cur++;
	}
	return res;
}
 
struct SegTree{
	int n; vector<node> seg;
	SegTree(int _n){
		seg.resize(4 * (n = _n) + 4);
		for(node &x : seg){
			x.s.insert({0,0});
		}
	};
	void upd(int v,int tl,int tr,int pos,int x){
		if(tl > pos || tr < pos) return;
		if(tl == pos && tr == pos){
			auto it = seg[v].s.upper_bound({x,0}); it--;
			seg[v].s.insert({x,it -> ss + 1}); 
			return;
		}
		int tm = (tl + tr) / 2;
		upd(v*2,tl,tm,pos,x),upd(v*2+1,tm+1,tr,pos,x);
		seg[v] = merge(seg[v*2],seg[v*2+1]);
	}
	void upd(int pos,int x){
		upd(1,1,n,pos,x);
	}
	int get(int v,int tl,int tr,int l,int r,int x){
		if(tl > r || tr < l) return 0;
		if(tl >= l && tr <= r){
			return seg[v].s.size() - prev(seg[v].s.lower_bound({x,0})) -> ss - 1;
		}
		int tm = (tl + tr) / 2;
		return get(v*2,tl,tm,l,r,x) + get(v*2+1,tm+1,tr,l,r,x);
	}
	int get(int pos,int x){
		return get(1,1,n,pos,n,x);
	}
};
 
void solve(){
 
	int n,t;
	cin >> n >> t;
 
	vector<int> nums,ans(t + 1); vector<pair<int,int>> v(n);
	for(auto &[x,y] : v){
		cin >> x >> y;
		nums.pb(y);
	} 
 
	vector<array<int,4>> q(t); int pos = 0;
	for(auto &[x,y,z,t] : q){
		cin >> x >> y >> z; t = ++pos;
	}
 
	auto f = [&](int x){
		return lower_bound(all(nums),x) - nums.begin() + 1;
	};
 
	sort(all(nums)), sort(rall(v)), sort(rall(q));
	nums.resize(unique(all(nums)) - nums.begin());
 
	pos = -1; SegTree seg(nums.size());
	for(auto[x,y,z,t] : q){
		while(pos + 1 < n && v[pos+1].ff >= x){
			++pos; seg.upd(f(v[pos].ss),v[pos].ss + v[pos].ff); 
		}
		ans[t] = seg.get(f(y),z); 
	}
 
	for(int i = 1; i <= t; i++){
		cout << ans[i] << endl;
	}
}
 
signed main(){	
 		
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2223 ms 4728 KB Output is correct
8 Correct 2244 ms 4904 KB Output is correct
9 Correct 2229 ms 5024 KB Output is correct
10 Incorrect 2064 ms 1928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 38804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 38804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2223 ms 4728 KB Output is correct
8 Correct 2244 ms 4904 KB Output is correct
9 Correct 2229 ms 5024 KB Output is correct
10 Incorrect 2064 ms 1928 KB Output isn't correct
11 Halted 0 ms 0 KB -