oj.uz

Submission #131445

# Submission time Handle Problem Language Result Execution time Memory
131445 2019-07-17T07:20:06 Z MrTEK Examination (JOI19_examination) C++14
0 / 100
 3000 ms 203576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

using namespace __gnu_pbds;
using ordered_set = tree<ii, null_type,less<ii>, rb_tree_tag,tree_order_statistics_node_update>;

const int N = 2e5 + 5;
const int inf = 2e9 + 500;

vector <int> v;
vector <pair<ii,ii>> queries;
map <int,int> id;
int answer,n,q,s[N],t[N],x[N],y[N],z[N],ans[N],tim;
ordered_set seg[N << 2];

void update(int ind,int l,int r,int w,int val) {
	if (l > w || r < w)
		return;
	seg[ind].insert({-val,++tim});
	if (l == r)
		return;
	int mid = (l + r) / 2;
	update(ind + ind,l,mid,w,val);
	update(ind + ind + 1,mid + 1,r,w,val);
}

void query(int ind,int l,int r,int lw,int rw,int val) {
	if (l > rw || r < lw)
		return;
	if (l >= lw && r <= rw) {
		answer += seg[ind].order_of_key({-val,-inf});
		return;
	}
	int mid = (l + r) / 2;
	query(ind + ind,l,mid,lw,rw,val);
	query(ind + ind + 1,mid + 1,r,lw,rw,val);
}

int query(int x,int val) {
	answer = 0;
	query(1,1,n + q,x,n + q,val);
	return answer;
}

int main() {
	cin >> n >> q;
	for (int i = 1 ; i <= n ; i++) {
		cin >> s[i] >> t[i];
		v.push_back(t[i]);
		queries.push_back({{s[i],inf},{t[i],s[i] + t[i]}});
	}
	for (int i = 1 ; i <= q ; i++) {
		cin >> x[i] >> y[i] >> z[i];
		v.push_back(y[i]);
		queries.push_back({{x[i],i},{y[i],z[i]}});
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end()) - v.begin());
	int dsa = 0;
	for (auto i : v) {
		id[i] = ++dsa;
		// cerr << dsa << ". " << i << endl;
	}
	sort(queries.begin(),queries.end());
	reverse(queries.begin(),queries.end());
	for (auto i : queries) {
		if (i.first.second == inf) {
			// cerr << "update -> " << i.second.first << " " << i.second.second << endl;
			update(1,1,n + q,id[i.second.first],i.second.second);
		}
		else {
			// cerr << "query -> " << i.second.first << " " << i.second.second << endl;
			ans[i.first.second] = query(id[i.second.first],i.second.second);
		}
	}
	for (int i = 1 ; i <= q ; i++)
		cout << ans[i] << "\n";
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 75512 KB Output is correct
2 Correct 99 ms 75476 KB Output is correct
3 Correct 99 ms 75640 KB Output is correct
4 Correct 98 ms 75512 KB Output is correct
5 Correct 109 ms 75588 KB Output is correct
6 Correct 105 ms 75512 KB Output is correct
7 Correct 142 ms 78840 KB Output is correct
8 Correct 143 ms 78712 KB Output is correct
9 Correct 150 ms 78712 KB Output is correct
10 Correct 139 ms 78432 KB Output is correct
11 Correct 136 ms 78584 KB Output is correct
12 Incorrect 130 ms 78332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 75512 KB Output is correct
2 Correct 99 ms 75476 KB Output is correct
3 Correct 99 ms 75640 KB Output is correct
4 Correct 98 ms 75512 KB Output is correct
5 Correct 109 ms 75588 KB Output is correct
6 Correct 105 ms 75512 KB Output is correct
7 Correct 142 ms 78840 KB Output is correct
8 Correct 143 ms 78712 KB Output is correct
9 Correct 150 ms 78712 KB Output is correct
10 Correct 139 ms 78432 KB Output is correct
11 Correct 136 ms 78584 KB Output is correct
12 Incorrect 130 ms 78332 KB Output isn't correct
13 Halted 0 ms 0 KB -