| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 725771 | josanneo22 | Alternating Heights (CCO22_day1problem1) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(){
int x=0,w=1;
char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
/*
subtask 1 idea: since k=2, meaning that the array must have only 1 or 2
so we can just check whether it is alternating 1 2 1 2 1 2 or 2 1 2 1 2 1
this can be done in O(n^2)
subtask 2&3 idea: let the array be something like:
a>b b>c c>a
we can define an edge from a to b if a>b
a->b->c
| |
<------
which we can easily relate it to rock paper scissors
meaning the answer is yes if and only if it doesn't form a cycle
subtask 4: for each i in the array we just check the furthest r such that it doesn't
form a cycle, just need to find cycles o(n) for each i
overall O(n^2)
*/
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
bool has_cycle(vector<vector<int>>& adj) {
int n = sz(adj);
vector<int> deg(n);
for (int a = 0; a < n; a++)
for (int b : adj[a])
deg[b]++;
vector<int> q; q.reserve(n);
for (int i = 0; i < n; i++) if (deg[i] == 0) q.push_back(i);
for (int rep = 0; rep < sz(q); rep++) {
int c = q[rep];
for (auto nxt : adj[c]) {
deg[nxt]--;
if (deg[nxt] == 0)
q.push_back(nxt);
}
}
return sz(q) < n;
}
void solve(){
int n, k, q; cin >> n >> k >> q;
vector<int> a(n); for (auto& x : a) cin >> x, --x;
vector<int> can(n);
for (int rep : {0, 1}) {
for (int l = rep, r = l; l < n; l += 2) {
while (r < n) {
vector<vector<int>> adj(k);
for (int i = l; i < r; i++) {
if (i % 2 == l % 2) adj[a[i]].push_back(a[i + 1]);
else adj[a[i + 1]].push_back(a[i]);
}
if (has_cycle(adj)) break;
r++;
}
can[l] = r;
}
}
while (q--) {
int l, r; cin >> l >> r, --l, --r;
if (can[l] <= r) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int tt=1; //cin>>tt;
while(tt--){
solve();
}
}