Submission #411727

#	Time	Username	Problem	Language	Result	Execution time	Memory
411727		abdzag	Werewolf (IOI18_werewolf)	C++17	0 / 100	164 ms	30956 KiB

werewolf

#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define  sz(a) a.size()
typedef long double ld;
using namespace std;
static const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;
struct segtree {
    vector<multiset<pair<ll,ll>>> s;
    ll n;
    segtree(ll n=0) : s(2*n) ,n(n){}
    void update(ll pos, ll val, ll nxt) {
        ll i = pos;
        for (pos += n; pos;) {
            auto it = s[pos].find(make_pair(val,i));
            if (it != s[pos].end())s[pos].erase(it);
            s[pos].insert(make_pair(nxt,i));
            pos /= 2;
        }
    }
    pair<ll,ll> query_bigger(ll l, ll r, ll val) {
        pair<ll,ll> a = make_pair(inf,inf), b = make_pair(inf,inf);
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l % 2) {
                auto it = s[l].lower_bound(make_pair(val, -inf));
                if (it != s[l].end()) {
                    a = min(a, *it);
                }
                l++;
            }
            if (r % 2) {
                auto it = s[--r].lower_bound(make_pair(val, -inf));
                if (it != s[r].end()) {
                    b = min(b, *it);
                }
                
            }
        }
        return min(a, b);
    }
    pair<ll, ll> query_smaller(ll l, ll r, ll val) {
        pair<ll, ll> a = make_pair(-inf, -inf), b = make_pair(-inf, -inf);
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l % 2) {
                auto it = s[l].lower_bound(make_pair(val, -inf));
                if (it != s[l].begin()) {
                    a = max(a, (*--it));
                }
                l++;
            }
            if (r % 2) {
                auto it = s[--r].lower_bound(make_pair(val, -inf));
                if (it != s[r].begin()) {
                    b = max(b, (*--it));
                }

            }
        }
        return max(a, b);
    }

};
vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
    std::vector<int> S, std::vector<int> E,
    std::vector<int> L, std::vector<int> R) {
    vector<ll> v;
    vector<vector<ll>> g;
    vector<ll> howmany(N);
    rep(i, 0, X.size()) {
        howmany[X[i]]++;
        howmany[Y[i]]++;
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    rep(i, 0, N) {
        if (howmany[i] == 1) {
            v.push_back(i);
            break;
        }
    }
    v.push_back(g[v[0]][0]);
    rep(i, 1, N) {
        if (g[v[i]][0] != v[i - 1]) {
            v.push_back(g[v[i]][0]);
        }
        else v.push_back(g[v[i]][1]);
    }
    segtree tree(N);
    rep(i, 0, N) {
        tree.update(i, -1, v[i]);
    }
    vector<ll> maping(N);
    rep(i, 0, v.size())maping[v[i]] = i;
    vector<int> ans(E.size());
    rep(i, 0, E.size()) {
        if (tree.query_smaller(maping[S[i]], maping[E[i]], L[i]).second >= tree.query_bigger(maping[S[i]], maping[E[i]], R[i]).second)ans[i] = 1;
    }
    return ans;
}

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