oj.uz

Submission #131624

# Submission time Handle Problem Language Result Execution time Memory
131624 2019-07-17T10:41:49 Z MrTEK Examination (JOI19_examination) C++14
2 / 100
 3000 ms 206176 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) {
	seg[ind].insert({-val,++tim});
	if (l == r)
		return;
	int mid = (l + r) / 2;
	if (mid >= w)
	update(ind + ind,l,mid,w,val);
	if (mid + 1 <= w)
	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 >= lw && r <= rw) {
		answer += seg[ind].order_of_key({-val,inf});
		return;
	}
	int mid = (l + r) / 2;
	if(mid >= lw) query(ind + ind,l,mid,lw,rw,val);
	if(mid+1<=rw) 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() {
	// freopen("04-01.txt","r",stdin);
	// freopen("04-01o2.txt","w",stdout);
	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 105 ms 75640 KB Output is correct
2 Correct 106 ms 75532 KB Output is correct
3 Correct 100 ms 75512 KB Output is correct
4 Correct 114 ms 75512 KB Output is correct
5 Correct 99 ms 75512 KB Output is correct
6 Correct 99 ms 75640 KB Output is correct
7 Correct 144 ms 78744 KB Output is correct
8 Correct 143 ms 78744 KB Output is correct
9 Correct 143 ms 78712 KB Output is correct
10 Correct 157 ms 78456 KB Output is correct
11 Correct 145 ms 78712 KB Output is correct
12 Correct 132 ms 78312 KB Output is correct
13 Correct 168 ms 78712 KB Output is correct
14 Correct 144 ms 78712 KB Output is correct
15 Correct 142 ms 78856 KB Output is correct
16 Correct 131 ms 78772 KB Output is correct
17 Correct 138 ms 78456 KB Output is correct
18 Correct 134 ms 78364 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 75640 KB Output is correct
2 Correct 106 ms 75532 KB Output is correct
3 Correct 100 ms 75512 KB Output is correct
4 Correct 114 ms 75512 KB Output is correct
5 Correct 99 ms 75512 KB Output is correct
6 Correct 99 ms 75640 KB Output is correct
7 Correct 144 ms 78744 KB Output is correct
8 Correct 143 ms 78744 KB Output is correct
9 Correct 143 ms 78712 KB Output is correct
10 Correct 157 ms 78456 KB Output is correct
11 Correct 145 ms 78712 KB Output is correct
12 Correct 132 ms 78312 KB Output is correct
13 Correct 168 ms 78712 KB Output is correct
14 Correct 144 ms 78712 KB Output is correct
15 Correct 142 ms 78856 KB Output is correct
16 Correct 131 ms 78772 KB Output is correct
17 Correct 138 ms 78456 KB Output is correct
18 Correct 134 ms 78364 KB Output is correct
19 Execution timed out 3054 ms 206176 KB Time limit exceeded
20 Halted 0 ms 0 KB -