oj.uz

Submission #387596

# Submission time Handle Problem Language Result Execution time Memory
387596 2021-04-09T03:04:35 Z 8e7 Trampoline (info1cup20_trampoline) C++14
100 / 100
 601 ms 41212 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <assert.h>
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
vector<int> xv;
pii orig[maxn];

pii pos[maxn];
vector<int> pnt[maxn], ind[maxn];
bool con[maxn];
int to[18][maxn];

int main() {
	io
	int r, c, n;
	cin >> r >> c >> n;
	for (int i = 0;i < n;i++) {
		cin >> orig[i].ff >> orig[i].ss;
		xv.push_back(orig[i].ff);
	}
	sort(xv.begin(), xv.end());
	xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
	//for (int i:xv) cout << i << endl;
	for (int i = 0;i < n;i++) {
		int posid = lower_bound(xv.begin(), xv.end(), orig[i].ff) - xv.begin();
		pnt[posid].push_back(orig[i].ss);
	}

	int tot = 1;
	for (int i = 0;i < xv.size();i++) {
		sort(pnt[i].begin(), pnt[i].end());
		for (int j = 0;j < pnt[i].size();j++) {
			pos[tot] = make_pair(i, pnt[i][j]);
			ind[i].push_back(tot++);
		}

		if (i < xv.size() - 1) {
			con[i] = xv[i + 1] == xv[i] + 1 ? 1 : 0;
		}
	}
	pos[tot] = make_pair(maxn - 2, c + 1);
	for (int i = 1;i < tot;i++) {
		if (con[pos[i].ff]) {
			int id = lower_bound(pnt[pos[i].ff + 1].begin(), pnt[pos[i].ff + 1].end(), pos[i].ss) - pnt[pos[i].ff + 1].begin();
			if (id >= ind[pos[i].ff + 1].size()) {
				to[0][i] = tot;
			} else {
				to[0][i] = ind[pos[i].ff + 1][id];
			}
		} else {
			to[0][i] = tot;
		}
	}
	to[0][tot] = tot;
	for (int i = 1;i < 18;i++) {
		for (int j = 1;j <= tot;j++) to[i][j] = to[i - 1][to[i - 1][j]];
	}

	int t;
	cin >> t;
	while (t--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) {
			cout << "No" << "\n";
			continue;
		}
		if (x1 == x2) {
			cout << (y1 <= y2 ? "Yes" : "No") << "\n";
		} else {
			int comp = lower_bound(xv.begin(), xv.end(), x1) - xv.begin();
			int ans = 1;
			if (comp >= xv.size()) {
				ans = 0;
			} else if (xv[comp] != x1) {
				ans = 0;
			} else {
				x2--;
				int dif = x2 - x1;
				int id = lower_bound(pnt[comp].begin(), pnt[comp].end(), y1) - pnt[comp].begin();
				if (id >= ind[comp].size() || dif >= maxn) {
					ans = 0;
				} else {
					int cur = ind[comp][id], cnt = 0;
					while (dif) {
						if (dif & 1) cur = to[cnt][cur];
						cnt++, dif>>=1;
					}
					if (pos[cur].ss > y2) {
						ans = 0;
					}
				}
			}

			cout << (ans ? "Yes" : "No") << "\n";
		}
	}
}
/*
4 5 2
1 2
3 4
3
2 1 4 5
1 2 1 4
3 3 4 4

 */

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0;i < xv.size();i++) {
      |                 ~~^~~~~~~~~~~
trampoline.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int j = 0;j < pnt[i].size();j++) {
      |                  ~~^~~~~~~~~~~~~~~
trampoline.cpp:50:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   if (i < xv.size() - 1) {
      |       ~~^~~~~~~~~~~~~~~
trampoline.cpp:58:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    if (id >= ind[pos[i].ff + 1].size()) {
      |        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    if (comp >= xv.size()) {
      |        ~~~~~^~~~~~~~~~~~
trampoline.cpp:94:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     if (id >= ind[comp].size() || dif >= maxn) {
      |         ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10700 KB 200 token(s): yes count is 21, no count is 179
2 Correct 12 ms 10828 KB 200 token(s): yes count is 70, no count is 130
3 Correct 9 ms 10524 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 30492 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 103 ms 30308 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 96 ms 29892 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 103 ms 30432 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 30528 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 252 ms 30372 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 251 ms 30320 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 262 ms 30656 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 273 ms 30692 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 345 ms 33088 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 12 ms 10360 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 12 ms 10316 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 13 ms 10572 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 12 ms 10316 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 13 ms 10424 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 12 ms 10316 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 501 ms 33652 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 447 ms 31420 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 282 ms 30276 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 601 ms 41212 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 372 ms 34368 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 277 ms 30460 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 300 ms 30532 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 275 ms 30192 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 492 ms 33240 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 513 ms 32924 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 565 ms 36924 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 264 ms 30764 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 262 ms 30716 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 347 ms 30788 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 252 ms 30628 KB 200000 token(s): yes count is 129674, no count is 70326