oj.uz

Submission #131462

# Submission time Handle Problem Language Result Execution time Memory
131462 2019-07-17T07:30:06 Z MrTEK Examination (JOI19_examination) C++14
2 / 100
 3000 ms 166212 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 = 1e5 + 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;
	sort(queries.begin(),queries.end());
	reverse(queries.begin(),queries.end());
	for (auto i : queries) {
		if (i.first.second == inf)
			update(1,1,n + q,id[i.second.first],i.second.second);
		else
			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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 38008 KB Output is correct
2 Correct 51 ms 37936 KB Output is correct
3 Correct 51 ms 38008 KB Output is correct
4 Correct 51 ms 38008 KB Output is correct
5 Correct 60 ms 38008 KB Output is correct
6 Correct 53 ms 37880 KB Output is correct
7 Correct 82 ms 41080 KB Output is correct
8 Correct 83 ms 41084 KB Output is correct
9 Correct 83 ms 41156 KB Output is correct
10 Correct 78 ms 40824 KB Output is correct
11 Correct 78 ms 41080 KB Output is correct
12 Correct 76 ms 40824 KB Output is correct
13 Correct 81 ms 41080 KB Output is correct
14 Correct 81 ms 41208 KB Output is correct
15 Correct 81 ms 41080 KB Output is correct
16 Correct 73 ms 41080 KB Output is correct
17 Correct 80 ms 40824 KB Output is correct
18 Correct 76 ms 40824 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 38008 KB Output is correct
2 Correct 51 ms 37936 KB Output is correct
3 Correct 51 ms 38008 KB Output is correct
4 Correct 51 ms 38008 KB Output is correct
5 Correct 60 ms 38008 KB Output is correct
6 Correct 53 ms 37880 KB Output is correct
7 Correct 82 ms 41080 KB Output is correct
8 Correct 83 ms 41084 KB Output is correct
9 Correct 83 ms 41156 KB Output is correct
10 Correct 78 ms 40824 KB Output is correct
11 Correct 78 ms 41080 KB Output is correct
12 Correct 76 ms 40824 KB Output is correct
13 Correct 81 ms 41080 KB Output is correct
14 Correct 81 ms 41208 KB Output is correct
15 Correct 81 ms 41080 KB Output is correct
16 Correct 73 ms 41080 KB Output is correct
17 Correct 80 ms 40824 KB Output is correct
18 Correct 76 ms 40824 KB Output is correct
19 Execution timed out 3090 ms 166212 KB Time limit exceeded
20 Halted 0 ms 0 KB -