Submission #966173

#	Time	Username	Problem	Language	Result	Execution time	Memory
966173		blackslex	Alternating Heights (CCO22_day1problem1)	C++17	0 / 25	586 ms	8628 KiB

Main

#include<bits/stdc++.h>

using namespace std;

int n, k, q, x, y;

int main() {
    scanf("%d %d %d", &n, &k, &q);
    vector<int> a(n + 5), dp(n + 5); iota(dp.begin(), dp.end(), 0);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        auto ck = [&] (int l, int r) {
            vector<vector<int>> v(n + 5, vector<int>());
            vector<int> deg(n + 5);
            for (int i = l; i < r; i++) {
                if ((i & 1) == (l & 1)) v[a[i]].emplace_back(a[i + 1]), deg[a[i + 1]]++;
                else v[a[i + 1]].emplace_back(a[i]), deg[a[i]]++;
            }
            queue<int> q;
            for (int i = l; i <= r; i++) if (!deg[a[i]]) q.emplace(a[i]);
            while (!q.empty()) {
                int cur = q.front(); q.pop();
                for (auto &e: v[cur]) if (!(--deg[e])) q.emplace(e);
            }
            for (int i = l; i <= r; i++) if (deg[a[i]]) return 1;
            return 0;
        };
        int l = i, r = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (!ck(i, mid)) l = mid + 1;
            else r = mid - 1;
        }
        dp[i] = r;
    }
    while (q--) scanf("%d %d", &x, &y), printf("%s\n", dp[x] >= y ? "YES" : "NO");
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:10:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
Main.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     while (q--) scanf("%d %d", &x, &y), printf("%s\n", dp[x] >= y ? "YES" : "NO");
      |                 ~~~~~^~~~~~~~~~~~~~~~~

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