Submission #984687

#	Time	Username	Problem	Language	Result	Execution time	Memory
984687		wood	Werewolf (IOI18_werewolf)	C++17	0 / 100	823 ms	39500 KiB

werewolf

#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#pragma comment(linker, "/STACK: 2000000")
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay

//the only time I thought this could be solved wihtout segment trees segment tree was the answer fml
constexpr int N = 2e6+100; //change

struct segtree
{
    int mx[N] = {0}, mn[N], size = 1;
    segtree(int n){while(size<=n)size*=2; fill(mn,mn+N,INT_MAX);}
    void upd(int i, int u){
        upd(i,u,0,0,size);
    }
    void upd(int i, int u, int x, int l, int r){
        if(r-l==1){
            mx[x] = u;
            mn[x] = u;
            return;
        }
        int m = (r+l)/2;
        if(i<m) upd(i,u,2*x+1,l,m);
        else upd(i,u,2*x+2,m,r);
        mx[x] = max(mx[2*x+1],mx[2*x+2]);
        mn[x] = min(mn[2*x+1],mn[2*x+2]);
    }
    int get(int l, int r, bool MX){
        return get(l,r,0,0,size,MX);
    }
    int get(int l, int r, int x, int lx, int rx, bool MX){
        int* arr = (MX) ? mx : mn;
        if(lx>=r||rx<=l) return (MX) ? 0 : INT_MAX;
        else if(lx>=l&&rx<=r) return arr[x];
        int m = (rx+lx)/2;
        int p = get(l,r,2*x+1,lx,m,MX);
        int q = get(l,r,2*x+2,m,rx,MX);
        if(MX) return max(p,q);
        else return min(p,q);
    }
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    int n = N,m = X.size(),q = S.size();
    vi adj[n];
    for (size_t i = 0; i < m; i++)
    {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    vi arr;
    for (size_t i = 0; i < N; i++)
    {
        if(adj[i].size()<=1){
            int e = -1,x = i ;
            while(arr.size()<N){
                arr.pb(x);
                for(int p : adj[x]){
                    if(p!=e){
                        e = x;
                        x = p;
                        break;
                    }
                }
            }
            break;
        }
    }
    segtree sg(n);
    int ind[n];
    for (size_t i = 0; i < n; i++)
    {
        sg.upd(i,arr[i]);
        ind[arr[i]] = i;
    }
    vi res;
    for (size_t i = 0; i < q; i++)
    {
        int from_start;
        if(S[i]<L[i]||E[i]>R[i]){
            res.pb(0);
            continue;
        }
        int s = ind[S[i]], e = ind[E[i]];
        //binary search segtree to get the range from start
        //and find the furthest index whose min is smaller than R
        if(s>e){
            int r = s, l = e;
            while(r-l>1){
                int mid = (r+l)/2;
                if(sg.get(mid,s+1,false)>=L[i]) r = mid;
                else l = mid;
            }
            if(arr[r]>R[i]||sg.get(e,l+1,true)>R[i])
                res.pb(0);
            else res.pb(1);
        }
        else{
            int l = s, r = e;
            while(r-l>1){
                int mid = (r+l)/2;
                if(sg.get(s,mid+1,false)>=L[i]) l = mid;
                else r = mid;
            }
            if(arr[l]>R[i]||sg.get(r,e+1,true)>R[i])
                res.pb(0);
            else res.pb(1);
        }
    }
    return res;
}

// int main()
// {
//     fast_cin();
//     #ifndef ONLINE_JUDGE
//         #ifdef _WIN32
//             freopen("input.in", "r", stdin);
//             freopen("input.out", "w", stdout);
//         #endif
//     #endif
//     int n,m,q;
//     cin>>n>>m>>q;
//     vi a,b;
//     for (size_t i = 0; i < m; i++)
//     {
//         int x,y; cin>>x>>y;
//         a.pb(x); b.pb(y);
//     }
//     vi s,e,l,r;
//     for (size_t i = 0; i < q; i++)
//     {
//         int x,y,t,u;
//         cin>>x>>y>>t>>u;
//         s.pb(x); e.pb(y); l.pb(t); r.pb(u);
//     }
//     for(int i : check_validity(n,a,b,s,e,l,r)) cout<<i<<'\n';
//     return 0;
// }

Compilation message (stderr)

werewolf.cpp:20: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
   20 | #pragma comment(linker, "/STACK: 2000000")
      | 
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:66:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     for (size_t i = 0; i < m; i++)
      |                        ~~^~~
werewolf.cpp:72:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t i = 0; i < N; i++)
      |                        ~~^~~
werewolf.cpp:76:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |             while(arr.size()<N){
      |                   ~~~~~~~~~~^~
werewolf.cpp:91:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
werewolf.cpp:97:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |     for (size_t i = 0; i < q; i++)
      |                        ~~^~~
werewolf.cpp:99:13: warning: unused variable 'from_start' [-Wunused-variable]
   99 |         int from_start;
      |             ^~~~~~~~~~

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