Submission #81517

#	Time	Username	Problem	Language	Result	Execution time	Memory
81517		zubec	Werewolf (IOI18_werewolf)	C++14	0 / 100	4030 ms	27836 KiB

werewolf

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

const int N = 200100;

vector <int> g[N];

int a[N], pos[N], t[2][N*4];

void update(int v, int l, int r, int pos, int x){
    if (l == r){
        t[0][v] = x;
        t[1][v] = x;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid)
        update(v+v, l, mid, pos, x); else
        update(v+v+1, mid+1, r, pos, x);
    t[0][v] = min(t[0][v+v], t[0][v+v+1]);
    t[1][v] = max(t[1][v+v], t[1][v+v+1]);
}

int getMn(int v, int l, int r, int tl, int tr){
    if (l > r || tl > r || l > tr || tl > tr)
        return 1e9;
    if (tl <= l && r <= tr){
        return t[0][v];
    }
    int mid = (l+r)>>1;
    return min(getMn(v+v, l, mid, tl, tr), getMn(v+v+1, mid+1, r, tl, tr));
}

int getMx(int v, int l, int r, int tl, int tr){
    if (l > r || tl > r || l > tr || tl > tr)
        return 0;
    if (tl <= l && r <= tr){
        return t[1][v];
    }
    int mid = (l+r)>>1;
    return max(getMx(v+v, l, mid, tl, tr), getMx(v+v+1, mid+1, r, tl, tr));
}

int getRMn(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (mid <= pos){
        return getRMn(v+v+1, mid+1, r, pos, x);
    }
    if (t[0][v+v] < x){
        return getRMn(v+v, l, mid, pos, x);
    }
    return getRMn(v+v+1, mid+1, r, pos, x);
}
int getLMn(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (pos <= mid+1)
        return getLMn(v+v, l, mid, pos, x);
    if (t[0][v+v+1] < x)
        return getLMn(v+v+1, mid+1, r, pos, x);
    return getLMn(v+v, l, mid, pos, x);
}

int getRMx(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (mid <= pos){
        return getRMx(v+v+1, mid+1, r, pos, x);
    }
    if (t[1][v+v] > x){
        return getRMx(v+v, l, mid, pos, x);
    }
    return getRMx(v+v+1, mid+1, r, pos, x);
}
int getLMx(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (pos <= mid+1)
        return getLMx(v+v, l, mid, pos, x);
    if (t[1][v+v+1] > x)
        return getLMx(v+v+1, mid+1, r, pos, x);
    return getLMx(v+v, l, mid, pos, x);
}

std::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) {
    for (int i = 0; i < N; i++){
        g[i].clear();
    }
    for (int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    int cur = 0;
    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            cur = i;
            break;
        }
    }
    int prev = -1;
    for (int i = 0; i < N; i++){
        pos[cur] = i;
        a[i] = cur;
        update(1, 0, N-1, i, cur);
        for (int j = 0; j < g[cur].size(); j++){
            int to = g[cur][j];
            if (to == prev)
                continue;
            prev = cur;
            cur = to;
            break;
        }
    }

    vector <int> A;
    for (int ii = 0; ii < S.size(); ii++){
        int s = S[ii], e = E[ii];
        int l = L[ii], r = R[ii];

        /*int x1 = getLMn(1, 0, N-1, pos[s], l);
        int y1 = getRMn(1, 0, N-1, pos[s], l);
        int x2 = getLMx(1, 0, N-1, pos[e], r);
        int y2 = getRMx(1, 0, N-1, pos[e], r);
        if (a[x1] < l)
            ++x1;
        if (a[y1] < l)
            --y1;
        if (a[x2] > r)
            ++x2;
        if (a[y2] > r)
            --y2;*/
        int x1, y1, x2, y2;
        int tl = 0, tr = pos[s];
        while(tl < tr){
            int mid = (tl+tr)>>1;
            if (getMn(1, 0, N-1, mid, pos[s]) < l)
                tl = mid+1; else
                tr = mid;
        }
        x1 = tl;
        tl = pos[s], tr = N-1;
        while(tl < tr){
            int mid = (tl+tr+1)>>1;
            if (getMn(1, 0, N-1, pos[s], mid) < l)
                tr = mid-1; else
                tl = mid;
        }
        y1 = tl;
        tl = 0, tr = pos[e];
        while(tl < tr){
            int mid = (tl+tr)>>1;
            if (getMx(1, 0, N-1, mid, pos[e]) > r)
                tl = mid+1; else
                tr = mid;
        }
        x2 = tl;
        tl = pos[e], tr = N-1;
        while(tl < tr){
            int mid = (tl+tr+1)>>1;
            if (getMx(1, 0, N-1, pos[e], mid) > r)
                tr = mid-1; else
                tl = mid;
        }
        y2 = tl;

        int bb = 0;
        //cout << "kek " << x1 << ' ' << y1 << "  " << x2 << ' ' << y2 << endl;
        int x3 = max(x1, x2);
        int y3 = min(y1, y2);
        if (x3 <= y3)
            bb = 1;

        A.push_back(bb);
    }

    return A;

}

/**

5 4 1
1 0
0 3
3 4
4 2
1 2 0 3

*/

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[cur].size(); j++){
                         ~~^~~~~~~~~~~~~~~
werewolf.cpp:126:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < S.size(); ii++){
                      ~~~^~~~~~~~~~

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