oj.uz

Submission #698302

# Submission time Handle Problem Language Result Execution time Memory
698302 2023-02-13T05:15:06 Z blackscreen1 Alternating Heights (CCO22_day1problem1) C++17
25 / 25
 357 ms 23448 KB 
#include <bits//stdc++.h>
using namespace std;
#define ll long long
#define st short
#define iloop(m, h) for (auto i = m; i != h; i+=(m<h?1:-1))
#define jloop(m, h) for (auto j = m; j != h; j+=(m<h?1:-1))
#define kloop(m, h) for (auto k = m; k != h; k+=(m<h?1:-1))
#define lloop(m, h) for (auto l = m; l != h; l+=(m<h?1:-1))
#define iloop_(m, h, g) for (auto i = m; i != h; i+=g)
#define jloop_(m, h, g) for (auto j = m; j != h; j+=g)
#define kloop_(m, h, g) for (auto k = m; k != h; k+=g)
#define lloop_(m, h, g) for (auto l = m; l != h; l+=g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll,ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, m, t;
ll adjmat[3005][3005];
ll vis[3005];
bool dfs(ll nd) {
	vis[nd] = 1;
	iloop(0, m) {
		if (adjmat[nd][i] && vis[i] == 1) return 0;
		if (adjmat[nd][i] && vis[i] == 0) if (dfs(i) == 0) return 0;
	}
	vis[nd] = 2;
	return 1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> t;
    ll a[n];
    iloop(0, n) {cin >> a[i]; a[i]--;}
    ll lptr = 0;
    ll ans[n];
    iloop(0, n) {
		if (i != 0) {
			if (i%2 == 1) {
				adjmat[a[i]][a[i-1]]++;
			}
			else {
				adjmat[a[i-1]][a[i]]++;
			}
		}
		while (1) {
			memset(vis, 0, sizeof(vis));
			if (dfs(a[i]) == 1) break;
			lptr++;
			if (lptr%2 == 1) {
				adjmat[a[lptr]][a[lptr-1]]--;
			}
			else {
				adjmat[a[lptr-1]][a[lptr]]--;
			}
		}
		ans[i] = lptr;
	}
	ll a1, b1;
	iloop(0, t) {
		cin >> a1 >> b1;
		a1--, b1--;
		if (ans[b1] > a1) cout << "NO\n";
		else cout << "YES\n";
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3372 KB Output is correct
2 Correct 154 ms 3352 KB Output is correct
3 Correct 153 ms 3408 KB Output is correct
4 Correct 116 ms 3240 KB Output is correct
5 Correct 124 ms 3484 KB Output is correct
6 Correct 157 ms 3292 KB Output is correct
7 Correct 151 ms 3344 KB Output is correct
8 Correct 155 ms 3432 KB Output is correct
9 Correct 150 ms 3408 KB Output is correct
10 Correct 158 ms 3796 KB Output is correct
11 Correct 149 ms 4400 KB Output is correct
12 Correct 155 ms 4276 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3404 KB Output is correct
2 Correct 137 ms 10964 KB Output is correct
3 Correct 136 ms 10956 KB Output is correct
4 Correct 113 ms 8208 KB Output is correct
5 Correct 129 ms 9464 KB Output is correct
6 Correct 145 ms 10988 KB Output is correct
7 Correct 146 ms 11016 KB Output is correct
8 Correct 138 ms 11036 KB Output is correct
9 Correct 148 ms 11392 KB Output is correct
10 Correct 137 ms 11920 KB Output is correct
11 Correct 144 ms 11836 KB Output is correct
12 Correct 0 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 98 ms 10544 KB Output is correct
3 Correct 181 ms 10468 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 103 ms 8812 KB Output is correct
8 Correct 56 ms 10088 KB Output is correct
9 Correct 293 ms 10012 KB Output is correct
10 Correct 46 ms 7924 KB Output is correct
11 Correct 42 ms 9852 KB Output is correct
12 Correct 45 ms 7204 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3372 KB Output is correct
2 Correct 154 ms 3352 KB Output is correct
3 Correct 153 ms 3408 KB Output is correct
4 Correct 116 ms 3240 KB Output is correct
5 Correct 124 ms 3484 KB Output is correct
6 Correct 157 ms 3292 KB Output is correct
7 Correct 151 ms 3344 KB Output is correct
8 Correct 155 ms 3432 KB Output is correct
9 Correct 150 ms 3408 KB Output is correct
10 Correct 158 ms 3796 KB Output is correct
11 Correct 149 ms 4400 KB Output is correct
12 Correct 155 ms 4276 KB Output is correct
13 Correct 136 ms 3404 KB Output is correct
14 Correct 137 ms 10964 KB Output is correct
15 Correct 136 ms 10956 KB Output is correct
16 Correct 113 ms 8208 KB Output is correct
17 Correct 129 ms 9464 KB Output is correct
18 Correct 145 ms 10988 KB Output is correct
19 Correct 146 ms 11016 KB Output is correct
20 Correct 138 ms 11036 KB Output is correct
21 Correct 148 ms 11392 KB Output is correct
22 Correct 137 ms 11920 KB Output is correct
23 Correct 144 ms 11836 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 98 ms 10544 KB Output is correct
27 Correct 181 ms 10468 KB Output is correct
28 Correct 4 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 103 ms 8812 KB Output is correct
32 Correct 56 ms 10088 KB Output is correct
33 Correct 293 ms 10012 KB Output is correct
34 Correct 46 ms 7924 KB Output is correct
35 Correct 42 ms 9852 KB Output is correct
36 Correct 45 ms 7204 KB Output is correct
37 Correct 348 ms 23448 KB Output is correct
38 Correct 357 ms 23372 KB Output is correct
39 Correct 166 ms 12764 KB Output is correct
40 Correct 112 ms 8268 KB Output is correct
41 Correct 133 ms 9772 KB Output is correct
42 Correct 237 ms 22864 KB Output is correct
43 Correct 251 ms 22332 KB Output is correct
44 Correct 232 ms 17304 KB Output is correct
45 Correct 189 ms 22860 KB Output is correct
46 Correct 189 ms 21956 KB Output is correct
47 Correct 191 ms 23116 KB Output is correct