oj.uz

답안 #131445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3062 ms 203576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3062 ms 203576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 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 -