oj.uz

Submission #131451

# Submission time Handle Problem Language Result Execution time Memory
131451 2019-07-17T07:22:02 Z MrTEK Examination (JOI19_examination) C++14
2 / 100
 3000 ms 203568 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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 75512 KB Output is correct
2 Correct 99 ms 75564 KB Output is correct
3 Correct 99 ms 75528 KB Output is correct
4 Correct 99 ms 75640 KB Output is correct
5 Correct 99 ms 75428 KB Output is correct
6 Correct 102 ms 75688 KB Output is correct
7 Correct 146 ms 78568 KB Output is correct
8 Correct 153 ms 78500 KB Output is correct
9 Correct 142 ms 78584 KB Output is correct
10 Correct 137 ms 78328 KB Output is correct
11 Correct 139 ms 78584 KB Output is correct
12 Correct 132 ms 78304 KB Output is correct
13 Correct 146 ms 78608 KB Output is correct
14 Correct 142 ms 78620 KB Output is correct
15 Correct 141 ms 78584 KB Output is correct
16 Correct 136 ms 78584 KB Output is correct
17 Correct 154 ms 78392 KB Output is correct
18 Correct 135 ms 78328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 203568 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 3026 ms 203568 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 75512 KB Output is correct
2 Correct 99 ms 75564 KB Output is correct
3 Correct 99 ms 75528 KB Output is correct
4 Correct 99 ms 75640 KB Output is correct
5 Correct 99 ms 75428 KB Output is correct
6 Correct 102 ms 75688 KB Output is correct
7 Correct 146 ms 78568 KB Output is correct
8 Correct 153 ms 78500 KB Output is correct
9 Correct 142 ms 78584 KB Output is correct
10 Correct 137 ms 78328 KB Output is correct
11 Correct 139 ms 78584 KB Output is correct
12 Correct 132 ms 78304 KB Output is correct
13 Correct 146 ms 78608 KB Output is correct
14 Correct 142 ms 78620 KB Output is correct
15 Correct 141 ms 78584 KB Output is correct
16 Correct 136 ms 78584 KB Output is correct
17 Correct 154 ms 78392 KB Output is correct
18 Correct 135 ms 78328 KB Output is correct
19 Execution timed out 3026 ms 203568 KB Time limit exceeded
20 Halted 0 ms 0 KB -