Submission #1043479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043479		Zicrus	Werewolf (IOI18_werewolf)	C++17	34 / 100	230 ms	44816 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

typedef long long ll;

ll n, m, q, pow2;
vector<vector<ll>> adj;
vector<ll> a, revA, segMin, segMax;

ll sMin(ll low, ll high) {
    low += pow2; high += pow2;
    ll res = n;
    while (low <= high) {
        if (low & 1) res = min(res, segMin[low++]);
        if (!(high & 1)) res = min(res, segMin[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

ll sMax(ll low, ll high) {
    low += pow2; high += pow2;
    ll res = -1;
    while (low <= high) {
        if (low & 1) res = max(res, segMax[low++]);
        if (!(high & 1)) res = max(res, segMax[high--]);
        low /= 2; high /= 2;
    }
    return res;
}

bool solve(ll s, ll e, ll l, ll r) {
    ll mid = pow2+s;
    while (mid > 1 && segMin[mid] >= l) {
        if ((mid & (mid+1)) == 0) break;
        if (mid & 1) mid++;
        mid /= 2;
    }
    while (mid < pow2) {
        if (segMin[2*mid] < l) mid = 2*mid;
        else mid = 2*mid+1;
    }
    mid = min(mid-pow2, e);
    if (a[mid] < l) mid--;
    return sMax(mid, e) <= r;
}

bool solveRev(ll s, ll e, ll l, ll r) {
    ll mid = pow2+e;
    while (mid > 1 && segMax[mid] <= r) {
        if ((mid & (mid+1)) == 0) break;
        if (mid & 1) mid++;
        mid /= 2;
    }
    while (mid < pow2) {
        if (segMax[2*mid] > r) mid = 2*mid;
        else mid = 2*mid+1;
    }
    mid = min(mid-pow2, s);
    if (a[mid] > r) mid--;
    return sMin(mid, s) >= l;
}

vector<int> check_validity(int n1, vector<int> x, vector<int> y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
    n = n1; m = x.size(); q = S.size();
    adj = vector<vector<ll>>(n);
    unordered_set<ll> deg1;
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
        if (!deg1.count(x[i])) deg1.insert(x[i]);
        else deg1.erase(x[i]);
        if (!deg1.count(y[i])) deg1.insert(y[i]);
        else deg1.erase(y[i]);
    }
    a = vector<ll>(n);
    revA = vector<ll>(n);
    pow2 = 1ll << (ll)ceil(log2(n));
    segMin = vector<ll>(2*pow2);
    segMax = vector<ll>(2*pow2);
    ll cur = *deg1.begin();
    vector<bool> vst(n);
    for (int i = 0; i < n; i++) {
        vst[cur] = true;
        //
        a[i] = segMin[pow2+i] = segMax[pow2+i] = cur;
        revA[cur] = i;
        //
        for (auto &e : adj[cur]) {
            if (vst[e]) continue;
            cur = e;
        }
    }
    for (int i = pow2-1; i > 0; i--) {
        segMin[i] = min(segMin[2*i], segMin[2*i+1]);
        segMax[i] = max(segMax[2*i], segMax[2*i+1]);
    }

    vector<int> res(q);
    while (q--) {
        ll s = revA[S[q]];
        ll e = revA[E[q]];
        ll l = L[q], r = R[q];
        res[q] = s < e ? solve(s, e, l, r) : solveRev(s, e, l, r);
    }
    return res;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51