oj.uz

Submission #666797

# Submission time Handle Problem Language Result Execution time Memory
666797 2022-11-29T18:03:39 Z Koful123 Examination (JOI19_examination) C++17
0 / 100
 3000 ms 44540 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 operator + (node other){
		node res; ms tmp = s;
		for(auto[x,y] : other.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] = 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(1e5 + 5);
	for(auto[x,y,z,t] : q){
		while(pos + 1 < n && v[pos+1].ff >= x){
			++pos; seg.upd(v[pos].ss,v[pos].ss + v[pos].ff); 
		}
		ans[t] = seg.get(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;
}

Compilation message

examination.cpp: In function 'void solve()':
examination.cpp:79:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   79 |  auto f = [&](int x){
      |       ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37836 KB Output is correct
2 Correct 31 ms 37808 KB Output is correct
3 Correct 31 ms 37824 KB Output is correct
4 Incorrect 30 ms 37844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 44540 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 3067 ms 44540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37836 KB Output is correct
2 Correct 31 ms 37808 KB Output is correct
3 Correct 31 ms 37824 KB Output is correct
4 Incorrect 30 ms 37844 KB Output isn't correct
5 Halted 0 ms 0 KB -