Submission #1246061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246061		vivkostov	Werewolf (IOI18_werewolf)	C++20	49 / 100	1655 ms	589824 KiB

werewolf

//#pragma once
//#include "grader.cpp"
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
    int a,b,l,r,ind;
};
struct group
{
    int l1,r1,l2,r2;
};
struct tree
{
    int in,l,r,st;
    tree(){}
};
bool cmp(cell a1,cell a2)
{
    return a1.ind<a2.ind;
}
bool cmp1(cell a1,cell a2)
{
    return a1.l>a2.l;
}
bool cmp2(cell a1,cell a2)
{
    return a1.r<a2.r;
}
int n,q,lamp,br,lead[200005],sz[200005],to,ind[200005],l[400005],r[400005],ql,qr,ql2,qr2,pos,num=1;
cell c[200005];
group g[200005];
tree p[50000005];
vector<int>v[200005],ver[400005],otg;
pair<int,int>point[200005];
void prec()
{
    for(int i=1;i<=n;i++)
    {
        lead[i]=i;
        ind[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=n*2;i++)
    {
        l[i]=0;
        r[i]=0;
        ver[i].clear();
    }
    br=n;
    pos=0;
}
int get_lead(int beg)
{
    if(lead[beg]==beg)return beg;
    return lead[beg]=get_lead(lead[beg]);
}
void add(int a,int b)
{
    a=get_lead(a);
    b=get_lead(b);
    if(a==b)return;
    if(sz[a]<sz[b])swap(a,b);
    br++;
    ver[br].push_back(ind[a]);
    ver[br].push_back(ind[b]);
    ind[a]=br;
    sz[a]+=sz[b];
    lead[b]=a;
}
void dfs(int beg)
{
    int w;
    l[beg]=1e9;
    for(int i=0;i<ver[beg].size();i++)
    {
        w=ver[beg][i];
        dfs(w);
        l[beg]=min(l[beg],l[w]);
        r[beg]=max(r[beg],r[w]);
    }
    if(ver[beg].size()==0)
    {
        pos++;
        l[beg]=pos;
        r[beg]=pos;
    }
    //cout<<l[beg]<<" "<<r[beg]<<" "<<beg<<endl;
}
void get_l()
{
    prec();
    sort(c+1,c+q+1,cmp2);
    int to=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(v[i][j]<i)add(i,v[i][j]);
        }
        while(to<=q&&c[to].r==i)
        {
            g[c[to].ind].r1=ind[get_lead(c[to].b)];
            to++;
        }
    }
    dfs(br);
    for(int i=1;i<=q;i++)
    {
        g[i].l1=l[g[i].r1];
        g[i].r1=r[g[i].r1];
    }
    for(int i=1;i<=n;i++)
    {
        point[i].first=l[i];
    }
}
void get_r()
{
    prec();
    sort(c+1,c+q+1,cmp1);
    int to=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(v[i][j]>i)add(i,v[i][j]);
        }
        while(to<=q&&c[to].l==i)
        {
            g[c[to].ind].r2=ind[get_lead(c[to].a)];
            to++;
        }
    }
    dfs(br);
    for(int i=1;i<=q;i++)
    {
        g[i].l2=l[g[i].r2];
        g[i].r2=r[g[i].r2];
    }
    for(int i=1;i<=n;i++)
    {
        point[i].second=r[i];
    }
}
void check(int h)
{
    if(!p[h].l)
    {
        num++;
        p[h].l=num;
        num++;
        p[h].r=num;
    }
}
void update2(int l,int r,int h)
{
    if(l>qr||r<qr)return;
    if(l==r)
    {
        p[h].st++;
        return;
    }
    check(h);
    if(qr<=(l+r)/2)
    {
        if(p[h].l==0)
        {
            num++;
            p[h].l=num;
        }
        update2(l,(l+r)/2,p[h].l);
    }
    else
    {
        if(p[h].r==0)
        {
            num++;
            p[h].r=num;
        }
        update2((l+r)/2+1,r,p[h].r);
    }
    p[h].st++;
}
void update1(int l,int r,int h)
{
    if(p[h].in==0)
    {
        num++;
        p[h].in=num;
    }
    update2(1,n,p[h].in);
    if(l==r)return;

    if(ql<=(l+r)/2)
    {
        if(p[h].l==0)
        {
            num++;
            p[h].l=num;
        }
        update1(l,(l+r)/2,p[h].l);
    }
    else
    {
        if(p[h].r==0)
        {
            num++;
            p[h].r=num;
        }
        update1((l+r)/2+1,r,p[h].r);
    }
}
int query2(int l,int r,int h)
{
    if(l>qr2||r<ql2)return 0;
    if(l>=ql2&&r<=qr2)return p[h].st;
    if(!p[h].l)return 0;
    return query2(l,(l+r)/2,p[h].l)+query2((l+r)/2+1,r,p[h].r);
}
int query1(int l,int r,int h)
{
    if(l>qr||r<ql||!p[h].in)return 0;
    if(l>=ql&&r<=qr)return query2(1,n,p[h].in);
    return query1(l,(l+r)/2,p[h].l)+query1((l+r)/2+1,r,p[h].r);
}
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;
    q=S.size();
    for(int i=1;i<=X.size();i++)
    {
        v[X[i-1]+1].push_back(Y[i-1]+1);
        v[Y[i-1]+1].push_back(X[i-1]+1);
    }
    for(int i=1;i<=q;i++)
    {
        c[i].a=S[i-1]+1;
        c[i].b=E[i-1]+1;
        c[i].l=L[i-1]+1;
        c[i].r=R[i-1]+1;
        c[i].ind=i;
    }
    get_l();
    get_r();
    for(int i=1;i<=n;i++)
    {
        ql=point[i].first;
        qr=point[i].second;
        update1(1,n,1);
    }
    for(int i=1;i<=q;i++)
    {
        ql=g[i].l1;
        qr=g[i].r1;
        ql2=g[i].l2;
        qr2=g[i].r2;
        if(query1(1,n,1))
        {
            otg.push_back(1);
        }
        else otg.push_back(0);
    }
    return otg;
}

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