Submission #1245326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245326		huydayy	Alternating Heights (CCO22_day1problem1)	C++20	4 / 25	137 ms	4416 KiB

Main

#include <bits/stdc++.h>
#define TASK "E"
#define int long long
#define double long double
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<ii>
#define reset(f, x) memset(f, x, sizeof(f))
#define all(x) x.begin(), x.end()
#define sz(x) (long long)x.size()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define FORV(v, H) for (auto &v: H)
#define __builtin_popcount __builtin_popcountll
#define BIT(mask, i) ((mask >> i) & 1ll)
#define MASK(i) (1ll << (i))
#define ONBIT(mask, i) (mask  (1ll << (i)))
#define OFFBIT(mask, i) (mask &~ (1ll << (i)))
#define mid(l, r) ((l + r) >> 1)
#define left(id) (id << 1)
#define right(id) ((id << 1)  1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define UNIQUE(x) sort(all(x)); x.resize(distance(x.begin(), unique(all(x))))
#define BUG1(a) cout << a << '\n'
#define BUG2(a, b) cout << a << " " << b << '\n'
#define BUG3(a, b, c) cout << a << " " << b << " " << c << '\n'
#define BUG4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << '\n'
#define BUG5(a, b, c, d, e) cout << a << " " << b << " " << c << " " << d << " " << e << '\n'
#define BUG6(a, b, c, d, e, f) cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << '\n'

using namespace std;

template <class X, class Y> bool maximize(X &A, const Y &B){
    if (A < B) return A = B, true;
    return false;
}

template <class X, class Y> bool minimize(X &A, const Y &B){
    if (A > B) return A = B, true;
    return false;
}

const int oo  = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 3e3 + 5;
const int LOG = 16;
const int base = 311;
const int BLOCK = 317;
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int N, K, Q;
int a[MAXN];

namespace Sub1{

    int ans[MAXN];

    void SOLVE(){
        FOR(l, 1, N){
            ans[l] = l;
            FOR(r, l + 1, N){
                if (a[r] == a[r - 1]) break;
                maximize(ans[l], r);
            }
        }
        FOR(i, 1, Q){
            int x, y;
            cin >> x >> y;
            cout << (ans[x] >= y ? "YES" : "NO") << '\n';
        }
    }

}

namespace Sub2{

    static const int MAXN = 500 + 5;

    int in[MAXN];
    bool ans[MAXN][MAXN];
    vi G[6];

    void SOLVE(){
        FOR(x, 1, N){
            ans[x][x] = 1;
            FOR(y, x + 1, N){
                int t = 1;
                FOR(u, x + 1, y){
                    if (t & 1) G[a[u]].push_back(a[u - 1]);
                    else G[a[u - 1]].push_back(a[u]);
                    t ^= 1;
                }
                FOR(u, 1, K){
                    FORV(v, G[u]) in[v]++;
                }
                int cnt = 0;
                queue <int> qu;
                FOR(u, 1, K) if (!in[u]) qu.push(u);
                while (sz(qu)){
                    int u = qu.front();
                    qu.pop();
                    cnt++;
                    FORV(v, G[u]){
                        if (!--in[v]) qu.push(v);
                    }
                }
                ans[x][y] = (cnt == K);
                FOR(u, x, y) in[u] = 0;
                FOR(u, 1, K) G[u].clear();
            }
        }
        FOR(i, 1, Q){
            int x, y;
            cin >> x >> y;
            cout << (ans[x][y] ? "YES" : "NO") << '\n';
        }
    }

}

void PROCESS(){
    if (K == 2) Sub1::SOLVE();
    else if (N <= 500 && K <= 5) Sub2::SOLVE();
}

main(){
    if (fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> K >> Q;
    FOR(i, 1, N) cin >> a[i];
    PROCESS();
    return 0;
}


















































/*
     ___  __    ___  _______   ___  ___          ________  ___  ________          ___  ___  ___  ___      ___    ___
    \  \\  \ |\  \|\  ___ \ |\  \|\  \        |\   ____\|\  \|\   __  \        |\  \|\  \|\  \|\  \    |\  \  / / |
    \ \  \/  /|\ \  \ \   __/|\ \  \\\  \       \ \  \___|\ \  \ \  \|\  \       \ \  \\\  \ \  \\\  \   \ \  \/ / /
     \ \   ___  \ \  \ \  \_|/_\ \  \\\  \       \ \  \  __\ \  \ \   __  \       \ \   __  \ \  \\\  \   \ \   / /
      \ \  \\ \  \ \  \ \  \_|\ \ \  \\\  \       \ \  \|\  \ \  \ \  \ \  \       \ \  \ \  \ \  \\\  \   \/  / /
       \ \__\\ \__\ \__\ \_______\ \_______\       \ \_______\ \__\ \__\ \__\       \ \__\ \__\ \_______\__/  / /
        \|__| \|__|\|__|\|_______|\|_______|        \|_______|\|__|\|__|\|__|        \|__|\|__|\|_______|\___/ /
                                                                                                        \|___|/
    Author: Kieu Gia Huy a.k.a kiwi
    From: C.H.V with luv <3
    ...

*/

Compilation message (stderr)

Main.cpp:131:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  131 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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