oj.uz

Submission #845025

# Submission time Handle Problem Language Result Execution time Memory
845025 2023-09-06T11:17:33 Z Piokemon Trampoline (info1cup20_trampoline) C++17
57 / 100
 651 ms 68936 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int N = 2e5;
constexpr int K = 19;
int jmp[N+9][K+9];
vector<pair<int,int>> poz[2*N+9];
map<int,int> nowe;
int stare[2*N+9];
int miejsce[2*N+9];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int r,c,n,t,x1,y1,x2,y2,nr=1;
	cin >> r >> c >> n;
	for (int x=1;x<=n;x++){
		cin >> x1 >> y1;
		miejsce[x] = y1;
		if (nowe[x1] == 0){
			stare[nr] = x1;
			nowe[x1] = nr++;
			poz[nr-1].push_back({1e9+9,0});
		}
		poz[nowe[x1]].push_back({y1,-x});
		if (nowe[x1+1] == 0){
			stare[nr] = x1+1;
			nowe[x1+1] = nr++;
			poz[nr-1].push_back({1e9+9,0});
		}
		poz[nowe[x1+1]].push_back({y1,x});
	}
	miejsce[0] = 1e9+9;
	for (int x=1;x<nr;x++) sort(poz[x].begin(),poz[x].end());
	vector<int> czeka;
	for (int x=1;x<nr;x++){
		czeka.clear();
		for (pair<int,int> y:poz[x]){
			if (y.second < 0){
				for (int z:czeka) jmp[z][0] = -y.second;
				czeka.clear();
			}
			else{
				czeka.push_back(y.second);
			}
		}
	}
	for (int k=1;k<K;k++){
		for (int x=1;x<=n;x++){
			jmp[x][k] = jmp[jmp[x][k-1]][k-1];
		}
	}
	cin >> t;
	while(t--){
		cin >> x1 >> y1 >> x2 >> y2;
		if (x2<x1 || y2<y1){
			cout << "No\n";
			continue;
		}
		if (x1==x2){
			cout << "Yes\n";
			continue;
		}
		if (nowe[x1] == 0){
			cout << "No\n";
			continue;
		}
		int temp = nowe[x1];
		int v,zost;
		int pocz,kon,srod;
		pocz = 0;
		kon = poz[temp].size()-1;
		while(pocz<kon){
			srod = (pocz+kon)/2;
			if (poz[temp][srod].first < y1) pocz = srod+1;
			else kon = srod;
		}
		if (poz[temp][pocz].second<0){
			zost = x2-x1-1;
			v = -poz[temp][pocz].second;
		}
		else{
			zost = x2-x1;
			v = poz[temp][pocz].second;
		}
		//cout << v << ' ' << zost << '\n';
		for (int k=0;k<K;k++){
			if (zost & (1<<k)) v = jmp[v][k];
		}
		if (miejsce[v] <= y2) cout << "Yes\n";
		else cout << "No\n";
	}
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 14936 KB expected YES, found NO [42nd token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 42416 KB expected YES, found NO [2299th token]
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 51372 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 190 ms 50960 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 193 ms 50972 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 235 ms 52496 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 236 ms 52272 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 421 ms 57316 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 7 ms 15192 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 10 ms 15704 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 6 ms 15192 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 10 ms 15192 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 6 ms 15192 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 58448 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 366 ms 54172 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 206 ms 51208 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 651 ms 68936 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 334 ms 57652 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 234 ms 50940 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 231 ms 50920 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 242 ms 50920 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 456 ms 57428 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 468 ms 57608 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 590 ms 62544 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 206 ms 51300 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 202 ms 51196 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 298 ms 52304 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 226 ms 51052 KB 200000 token(s): yes count is 129674, no count is 70326