Submission #725772

#	Time	Username	Problem	Language	Result	Execution time	Memory
725772		josanneo22	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	830 ms	13744 KiB

Main

#include<bits/stdc++.h>
using namespace std;
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();
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8