oj.uz

Submission #629994

# Submission time Handle Problem Language Result Execution time Memory
629994 2022-08-15T13:40:56 Z Arnch Examination (JOI19_examination) C++17
2 / 100
 1573 ms 115040 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e5 + 10, MOD = 1e9 + 7, SQ = 350;

int n, q; 
int x[N], y[N], sum[N];
int a[N], b[N], c[N];
int fen[SQ][N], cur[N];
int id[N], last[N];
int ans_t[N];

void compress() {
	vector<int> vc;
	for(int i = 0; i < n; i++) {
		vc.push_back(x[i]), vc.push_back(x[i] + y[i]);
	}
	for(int i = 0; i < q; i++) {
		vc.push_back(a[i]), vc.push_back(c[i]);
	}
	sort(All(vc));
	for(int i = 0; i < n; i++) {
		sum[i] = lower_bound(All(vc), x[i] + y[i]) - vc.begin();
		x[i] = lower_bound(All(vc), x[i]) - vc.begin();
	}	
	for(int i = 0; i < q; i++) {
		a[i] = lower_bound(All(vc), a[i]) - vc.begin();
		c[i] = lower_bound(All(vc), c[i]) - vc.begin();
	}

	vector<pair<int, int> > block, b2;
	for(int i = 0; i < n; i++) block.push_back({x[i], i});
	for(int i = 0; i < q; i++) b2.push_back({a[i], i});
	sort(All(block)), sort(All(b2));

	for(int i = n - 1; i >= 0; i--) {
		id[block[i].second] = i;
		while(!b2.empty() && b2.back().first > block[i].first) {
			last[b2.back().first] = i + 1;
			b2.pop_back();
		}
	}
	while(!b2.empty()) {
		last[b2.back().first] = 0;
		b2.pop_back();
	}
}
bool cmp(pair<int, int> i, pair<int, int> j) {
	int cnt1 = 0, cnt2 = 0;
	if(i.second == 0) cnt1 = y[i.first];
	else cnt1 = b[i.first];

	if(j.second == 0) cnt2 = y[j.first];
	else cnt2 = b[j.first];

	if(cnt1 != cnt2) return cnt1 > cnt2;
	return i.second < j.second;
}

void add_fen(int ind, int pos) {
	for(++pos; pos; pos -= (pos & -pos)) 
		fen[ind][pos]++;
}
int get_fen(int ind, int pos) {
	int ans = 0;
	for(++pos; pos < N; pos += (pos & -pos)) 
		ans += fen[ind][pos];
	return ans;
}

void add(int pos, int val) {
	cur[pos] = val;
	add_fen(pos / SQ, val);
}
int solve(int pos, int val) {
	int ans = 0;
	for(int i = pos; i / SQ == pos / SQ; i++) {
		if(cur[i] >= val) ans++;
	}	
	for(int i = pos / SQ + 1; i <= (n - 1) / SQ; i++) {
		ans += get_fen(i, val);
	}
	return ans;
}

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);

	cin >>n >>q;
	for(int i = 0; i < n; i++) cin >>x[i] >>y[i];
	for(int i = 0; i < q; i++) cin >>a[i] >>b[i] >>c[i];

	compress();

	vector<pair<int, int> > pos;
	for(int i = 0; i < n; i++) {
		pos.push_back(mak(i, 0));
	}
	for(int i = 0; i < q; i++) {
		pos.push_back(mak(i, 1));
	}
	sort(All(pos), cmp);

	memset(cur, -1, sizeof(cur));
	for(auto j : pos) {
		//cout<<j.first <<' ' <<j.second <<' ';
		//if(j.second == 0) cout<<sum[j.first] <<endl;
		//else cout<<c[j.first] <<endl;

		/*if(j.second == 0) {
			cout<<"^^" <<j.first <<' ' <<id[j.first] <<' ' <<sum[j.first] <<endl;
		} else {
			cout<<"***" <<j.first <<' ' <<last[a[j.first]] <<' ' <<c[j.first] <<endl;
		}*/
	
		if(j.second == 0) {
			add(id[j.first], sum[j.first]);
			continue;
		}
		ans_t[j.first] = solve(last[a[j.first]], c[j.first]);
	}

	for(int j = 0; j < q; j++)
		cout<<ans_t[j] <<endl;

	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 712 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 11 ms 1468 KB Output is correct
8 Correct 11 ms 1464 KB Output is correct
9 Correct 11 ms 1408 KB Output is correct
10 Correct 11 ms 1212 KB Output is correct
11 Correct 10 ms 1344 KB Output is correct
12 Correct 14 ms 1364 KB Output is correct
13 Correct 12 ms 1360 KB Output is correct
14 Correct 10 ms 1412 KB Output is correct
15 Correct 11 ms 1340 KB Output is correct
16 Correct 13 ms 1208 KB Output is correct
17 Correct 9 ms 1212 KB Output is correct
18 Correct 7 ms 1064 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1573 ms 115040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1573 ms 115040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 712 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 11 ms 1468 KB Output is correct
8 Correct 11 ms 1464 KB Output is correct
9 Correct 11 ms 1408 KB Output is correct
10 Correct 11 ms 1212 KB Output is correct
11 Correct 10 ms 1344 KB Output is correct
12 Correct 14 ms 1364 KB Output is correct
13 Correct 12 ms 1360 KB Output is correct
14 Correct 10 ms 1412 KB Output is correct
15 Correct 11 ms 1340 KB Output is correct
16 Correct 13 ms 1208 KB Output is correct
17 Correct 9 ms 1212 KB Output is correct
18 Correct 7 ms 1064 KB Output is correct
19 Incorrect 1573 ms 115040 KB Output isn't correct
20 Halted 0 ms 0 KB -