5346 | 2023. 04. 26 10:11:23 | Valaki2 | Színes szobák (50 pont) | cpp14 | Hibás válasz 4/50 | 37ms | 25320 KiB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 1e5;
int n, k, q;
int color[1 + maxn + 1];
vector<pii > steps;
bool stays(int idx, bool dir) {
for(pii s : steps) {
if(color[idx] == s.fi) {
idx += s.se;
}
if((idx > n) ^ dir) {
return true; // wrong direction
}
if((idx < 1) ^ dir) {
return false; // correct way
}
}
return true; // actually stays
}
void solve() {
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) {
cin >> color[i];
}
for(int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
steps.pb(mp(a, b));
}
int l = 0, r = n + 1;
while(l < r - 1) {
int mid = (l + r) / 2;
if(stays(mid, false)) {
r = mid;
} else {
l = mid;
}
}
int ans = 0;
ans += l;
l = 0, r = n + 1;
while(l < r - 1) {
int mid = (l + r) / 2;
if(stays(mid, true)) {
l = mid;
} else {
r = mid;
}
}
ans += n - l;
cout << ans << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 4/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1892 KiB | |||
2 | Hibás válasz | 0/0 | 37ms | 6340 KiB | |||
3 | Hibás válasz | 0/1 | 3ms | 3776 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 3736 KiB | |||
5 | Hibás válasz | 0/1 | 3ms | 3740 KiB | |||
6 | Elfogadva | 1/1 | 3ms | 4008 KiB | |||
7 | Hibás válasz | 0/1 | 3ms | 4252 KiB | |||
8 | Elfogadva | 1/1 | 3ms | 4484 KiB | |||
9 | Hibás válasz | 0/1 | 3ms | 4724 KiB | |||
10 | Elfogadva | 1/1 | 3ms | 5068 KiB | |||
11 | Hibás válasz | 0/1 | 3ms | 5204 KiB | |||
12 | Hibás válasz | 0/1 | 3ms | 5216 KiB | |||
13 | Hibás válasz | 0/1 | 4ms | 5600 KiB | |||
14 | Hibás válasz | 0/1 | 4ms | 5588 KiB | |||
15 | Hibás válasz | 0/1 | 4ms | 5872 KiB | |||
16 | Hibás válasz | 0/1 | 4ms | 6240 KiB | |||
17 | Hibás válasz | 0/1 | 6ms | 6404 KiB | |||
18 | Hibás válasz | 0/1 | 6ms | 6664 KiB | |||
19 | Hibás válasz | 0/1 | 21ms | 9136 KiB | |||
20 | Hibás válasz | 0/1 | 35ms | 11064 KiB | |||
21 | Hibás válasz | 0/1 | 26ms | 11344 KiB | |||
22 | Hibás válasz | 0/1 | 28ms | 13248 KiB | |||
23 | Hibás válasz | 0/1 | 34ms | 14608 KiB | |||
24 | Hibás válasz | 0/1 | 35ms | 15716 KiB | |||
25 | Hibás válasz | 0/1 | 35ms | 16904 KiB | |||
26 | Hibás válasz | 0/1 | 35ms | 18060 KiB | |||
27 | Hibás válasz | 0/3 | 35ms | 19096 KiB | |||
28 | Hibás válasz | 0/3 | 35ms | 20100 KiB | |||
29 | Hibás válasz | 0/3 | 35ms | 21104 KiB | |||
30 | Hibás válasz | 0/3 | 35ms | 22300 KiB | |||
31 | Hibás válasz | 0/3 | 34ms | 23552 KiB | |||
32 | Hibás válasz | 0/3 | 35ms | 24516 KiB | |||
33 | Hibás válasz | 0/4 | 17ms | 23652 KiB | |||
34 | Hibás válasz | 0/4 | 29ms | 25320 KiB |