oj.uz

Submission #131440

# Submission time Handle Problem Language Result Execution time Memory
131440 2019-07-17T07:18:03 Z MrTEK Examination (JOI19_examination) C++14
0 / 100
 3000 ms 204828 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 = 1e9;

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 100 ms 75640 KB Output is correct
2 Correct 100 ms 75512 KB Output is correct
3 Correct 98 ms 75512 KB Output is correct
4 Correct 100 ms 75640 KB Output is correct
5 Correct 101 ms 75512 KB Output is correct
6 Correct 99 ms 75500 KB Output is correct
7 Correct 154 ms 78968 KB Output is correct
8 Correct 143 ms 78840 KB Output is correct
9 Correct 146 ms 78860 KB Output is correct
10 Correct 151 ms 78416 KB Output is correct
11 Correct 143 ms 78596 KB Output is correct
12 Incorrect 132 ms 78408 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 3035 ms 204828 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 3035 ms 204828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 75640 KB Output is correct
2 Correct 100 ms 75512 KB Output is correct
3 Correct 98 ms 75512 KB Output is correct
4 Correct 100 ms 75640 KB Output is correct
5 Correct 101 ms 75512 KB Output is correct
6 Correct 99 ms 75500 KB Output is correct
7 Correct 154 ms 78968 KB Output is correct
8 Correct 143 ms 78840 KB Output is correct
9 Correct 146 ms 78860 KB Output is correct
10 Correct 151 ms 78416 KB Output is correct
11 Correct 143 ms 78596 KB Output is correct
12 Incorrect 132 ms 78408 KB Output isn't correct
13 Halted 0 ms 0 KB -