oj.uz

Submission #315236

# Submission time Handle Problem Language Result Execution time Memory
315236 2020-10-22T05:19:58 Z Jarif_Rahman Werewolf (IOI18_werewolf) C++17
34 / 100
 1295 ms 44520 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int n, m, q, k;
vector<vector<int>> v;
vector <pair<int, int>> se;
vector <pair<int, int>> lr;
vector <ll> mx, mn;
vector <ll> sth, inx;
void upd(int in, ll x){
    in+=k/2;
    mx[in] = x, mn[in] = x, in/=2;
    while(in > 0){
        mx[in] = max(mx[2*in], mx[2*in+1]);
        mn[in] = min(mn[2*in], mn[2*in+1]);
        in/=2;
    }
}
ll smx(int l, int r){
    l+=k/2, r+=k/2;
    ll s = -inf;
    while(l <= r){
        if(l%2 == 1) s = max(s, mx[l]), l++;
        if(r%2 == 0) s = max(s, mx[r]), r--;
        l/=2, r/=2;
    }
    return s;
}
ll smn(int l, int r){
    l+=k/2, r+=k/2;
    ll s = inf;
    while(l <= r){
        if(l%2 == 1) s = min(s, mn[l]), l++;
        if(r%2 == 0) s = min(s, mn[r]), r--;
        l/=2, r/=2;
    }
    return s;
}
ll fmx(int a, int b, ll x){
    int rr = -1;
    if(smx(a, b) <= x) return rr;
    while(1){
        if(b - a < 2){
            if(smx(a, a) > x) rr = a;
            else rr = b;
            break;
        }
        int md = (a+b)/2;
        if(smx(a, md) > x) b = md;
        else a = md+1;
    }
    return rr;
}
ll lmn(int a, int b, ll x){
    int rr = -1;
    if(smn(a, b) >= x) return rr;
    while(1){
        if(b - a < 2){
            if(smn(b, b) < x) rr = b;
            else rr = a;
            break;
        }
        int md = (a+b)/2;
        if(smn(md, b) < x) a = md;
        else b = md-1;
    }
    return rr;
}
ll lmx(int a, int b, ll x){
    int rr = -1;
    if(smx(a, b) <= x) return rr;
    while(1){
        if(b - a < 2){
            if(smx(b, b) > x) rr = b;
            else rr = a;
            break;
        }
        int md = (a+b)/2;
        if(smx(md, b) > x) a = md;
        else b = md-1;
    }
    return rr;
}
ll fmn(int a, int b, ll x){
    int rr = -1;
    if(smn(a, b) >= x) return rr;
    while(1){
        if(b - a < 2){
            if(smn(a, a) < x) rr = a;
            else rr = b;
            break;
        }
        int md = (a+b)/2;
        if(smn(a, md) < x) b = md;
        else a = md+1;
    }
    return rr;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = N, m = X.size(), q = S.size();
    for(int i = 0; i < q; i++){
        se.pb({S[i], E[i]});
        lr.pb({L[i], R[i]});
    }
    v = vector<vector<int>>(n);
    for(int i = 0; i < m; i++){
        v[X[i]].pb(Y[i]);
        v[Y[i]].pb(X[i]);
    }
    int a = -1;
    for(int i = 0; i < n; i++) if(v[i].size() == 1){
        a = i;
        break;
    }
    k = 1;
    while(k <= n) k*=2;
    k*=2;
    sth.pb(a);
    mx = vector<ll> (k, 0);
    mn = mx;
    int ls = -1, aa = a;
    while(v[aa].size() > 1 || aa == a){
        for(int x: v[aa]) if(x != ls){
            ls = aa;
            aa = x;
            sth.pb(aa);
            break;
        }
    }
    inx = sth;
    for(int i = 0; i < n; i++){
        upd(i, sth[i]);
        inx[sth[i]] = i;
    }
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        int s = se[i].f, e = se[i].sc, l = lr[i].f, r = lr[i].sc;
        int ss = inx[s], ee =inx[e];
        if(s < l) ans[i] = 0;
        else if(e > r) ans[i] = 0;
        else if(ss > ee){
            int a = fmx(ee, ss, r), b = lmn(ee, ss, l);
            if(a == -1 || b == -1) ans[i] = 1;
            else if(a - b < 2) ans[i] = 0;
            else ans[i] = 1;
        }
        else{
            int a = lmx(ss, ee, r), b = fmn(ss, ee, l);
            if(a == -1 || b == -1) ans[i] = 1;
            else if(b - a < 2) ans[i] = 0;
            else ans[i] = 1;
        }
    }
    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1270 ms 36084 KB Output is correct
2 Correct 714 ms 44504 KB Output is correct
3 Correct 701 ms 44376 KB Output is correct
4 Correct 891 ms 44380 KB Output is correct
5 Correct 945 ms 44504 KB Output is correct
6 Correct 1104 ms 44504 KB Output is correct
7 Correct 1261 ms 44520 KB Output is correct
8 Correct 675 ms 44396 KB Output is correct
9 Correct 537 ms 44336 KB Output is correct
10 Correct 584 ms 44376 KB Output is correct
11 Correct 629 ms 44372 KB Output is correct
12 Correct 657 ms 44500 KB Output is correct
13 Correct 967 ms 44468 KB Output is correct
14 Correct 1000 ms 44504 KB Output is correct
15 Correct 1008 ms 44500 KB Output is correct
16 Correct 1028 ms 44372 KB Output is correct
17 Correct 1295 ms 44440 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -