oj.uz

Submission #443607

# Submission time Handle Problem Language Result Execution time Memory
443607 2021-07-11T03:09:30 Z minhcool Examination (JOI19_examination) C++17
2 / 100
 3000 ms 282736 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define hash hash1
#define index indexx
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
const int hashy = 1e9 + 87;
 
/*
I think this is one of the easiest problems that you can give a guy if he knows segtree 2D
*/
 
// I think this will run as slow as f*ck, but it is sure O(1) lol
 
struct hash{
	int operator()(const ii&a)const{
		return ((a.fi % hashy) << 30) | (a.se % hashy);
	}
};
 
int n, q;
vector<pair<int, ii>> students;
vector<pair<iii, int>> queries;
 
int answer[N];
int cnt;
int IT[N * 20 * 20];
map<iiii, int> index;
 
int cal(int x1, int y1, int x2, int y2){
	if(index.find({{x1, y1}, {x2, y2}}) != index.end()) return index[{{x1, y1}, {x2, y2}}];
	cnt++;
	return index[{{x1, y1}, {x2, y2}}] = cnt;
}
 
void updy(int ind, int lx, int rx, int ly, int ry, int posy, int val){
	//cout << ind << " " << lx << " " << rx << " " << ly << " " << ry << "\n";
	IT[ind] += val;
	if(ly == ry) return;
	int mid = (ly + ry) >> 1;
	if(posy <= mid) updy(cal(lx, rx, ly, mid), lx, rx, ly, mid, posy, val);
	else updy(cal(lx, rx, mid + 1, ry), lx, rx, mid + 1, ry, posy, val);
}
 
void updx(int ind, int lx, int rx, int posx, int posy, int val){
	updy(ind, lx, rx, 1, (1LL << 30), posy, val);
	if(lx == rx) return;
	int mid = (lx + rx) >> 1;
	if(posx <= mid) updx(cal(lx, mid, 1, 1LL << 30), lx, mid, posx, posy, val);
	else updx(cal(mid + 1, rx, 1, 1LL << 30), mid + 1, rx, posx, posy, val);
	//int temp2 = cal(((long long)(mid + 1) << 30LL) + rx, 1LL << 31);
}
 
int gety(int lx, int rx, int ly, int ry, int Ly, int Ry){
	if(ly > Ry || ry < Ly) return 0;
	if(ly >= Ly && ry <= Ry){
		//cout << cal(((long long)lx << 20LL) + rx, ((long long)ly << 20LL) + ry) << " " << lx << " " << ly << " " << rx << " " << ry << " " << IT[cal(((long long)lx << 20LL) + rx, ((long long)ly << 20LL) + ry)] << "\n";
		//if(IT[cal(lx, rx, ly, ry)]) cout << lx << " " << rx << " " << ly << " " << ry << " " << Ly << " " << Ry << "\n";
		return IT[cal(lx, rx, ly, ry)];
	}
	int mid = (ly + ry) >> 1;
	return gety(lx, rx, ly, mid, Ly, Ry) + gety(lx, rx, mid + 1, ry, Ly, Ry);
}
 
int getx(int lx, int rx, int Lx, int Rx, int Ly, int Ry){
	if(lx > Rx || rx < Lx) return 0;
	if(lx >= Lx && rx <= Rx){
		//cout << lx << " " << rx << "\n";
		return gety(lx, rx, 1, 1LL << 30, Ly, Ry);
	}
	int mid = (lx + rx) >> 1;
	return getx(lx, mid, Lx, Rx, Ly, Ry) + getx(mid + 1, rx, Lx, Rx, Ly, Ry);
}
 
void process(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		int S, T;
		cin >> S >> T;
        S++;
        T++;
		students.pb({S + T, {S, T}});
	}
	for(int i = 1; i <= q; i++){
		int a, b, c;
		cin >> a >> b >> c;
        a++;
        b++;
        c += 2;
		queries.pb({{{c, a}, b}, i});
	}
	sort(students.begin(), students.end());
	sort(queries.begin(), queries.end());
	reverse(queries.begin(), queries.end());
	cal(1, 1LL << 30, 1, 1LL << 30);
	//return;
	for(auto it : queries){
		while(students.size() && it.fi.fi.fi <= students.back().fi){
			updx(1, 1, 1LL << 30, students.back().se.fi, students.back().se.se, 1);
			students.pop_back();
		}
		//cout << students.size() << "\n";
		answer[it.se] = getx(1, 1LL << 30, it.fi.fi.se, 1LL << 30, it.fi.se, 1LL << 30);
	}
	for(int i = 1; i <= q; i++) cout << answer[i] << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 4 ms 1228 KB Output is correct
7 Correct 1553 ms 282736 KB Output is correct
8 Correct 1534 ms 282388 KB Output is correct
9 Correct 1523 ms 282700 KB Output is correct
10 Correct 1341 ms 223184 KB Output is correct
11 Correct 1826 ms 223548 KB Output is correct
12 Correct 687 ms 868 KB Output is correct
13 Correct 1462 ms 278304 KB Output is correct
14 Correct 1463 ms 278916 KB Output is correct
15 Correct 1483 ms 278336 KB Output is correct
16 Correct 1366 ms 193540 KB Output is correct
17 Correct 1126 ms 195944 KB Output is correct
18 Correct 552 ms 720 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 4 ms 1228 KB Output is correct
7 Correct 1553 ms 282736 KB Output is correct
8 Correct 1534 ms 282388 KB Output is correct
9 Correct 1523 ms 282700 KB Output is correct
10 Correct 1341 ms 223184 KB Output is correct
11 Correct 1826 ms 223548 KB Output is correct
12 Correct 687 ms 868 KB Output is correct
13 Correct 1462 ms 278304 KB Output is correct
14 Correct 1463 ms 278916 KB Output is correct
15 Correct 1483 ms 278336 KB Output is correct
16 Correct 1366 ms 193540 KB Output is correct
17 Correct 1126 ms 195944 KB Output is correct
18 Correct 552 ms 720 KB Output is correct
19 Execution timed out 3074 ms 220848 KB Time limit exceeded
20 Halted 0 ms 0 KB -