제출 #993430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993430		modwwe	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	846 ms	103800 KiB

long_mansion

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int mod2=998244353;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
  // fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    ///modwwe
    phongbeo();
}
struct IT
{
    int t[2000001];
    void upd(int node,int l,int r,int l1,int r1,int c )
    {
        if(l1>r1) return;
        if(l>r1||r<l1)return;
        if(l>=l1&&r<=r1)
        {
            t[node]=c;
            return;
        }
        if(t[node]!=0)
        {
            t[node<<1]=t[node];
            t[node<<1|1]=t[node];
            t[node]=0;
        }
        int mid=l+r>>1;
        upd(node<<1,l,mid,l1,r1,c);
        upd(node<<1|1,mid+1,r,l1,r1,c);
    }
    int get(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return 0;
        if(l>=l1&&r<=r1) return t[node];
        if(t[node]!=0)
        {
            t[node<<1]=t[node];
            t[node<<1|1]=t[node];
            t[node]=0;
        }
        int mid=l+r>>1;
        return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1);
    }
} st1,st2;
struct IT2
{
    int  t[2000001];
    void reset(int node,int l,int r)
    {
        t[node]=n+1;
        if(l==r) return;
        int mid=l+r>>1;
        reset(node<<1,l,mid);
        reset(node<<1|1,mid+1,r);
    }
    void upd(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return ;
        if(l>=l1&&r<=r1)
        {
            t[node]=l;
            return;
        }
        int mid=l+r>>1;
        upd(node<<1,l,mid,l1,r1);
        upd(node<<1|1,mid+1,r,l1,r1);
        t[node]=max(t[node<<1],t[node<<1|1]);
    }
    void upd2(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return ;
        if(l>=l1&&r<=r1)
        {
            t[node]=l;
            return;
        }
        int mid=l+r>>1;
        upd2(node<<1,l,mid,l1,r1);
        upd2(node<<1|1,mid+1,r,l1,r1);
        t[node]=min(t[node<<1],t[node<<1|1]);
    }
    int get2(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return n+1;
        if(l>=l1&&r<=r1)return t[node];
        int mid=l+r>>1;
        return min(get2(node<<1,l,mid,l1,r1),get2(node<<1|1,mid+1,r,l1,r1));
    }
    int get(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return 0;
        if(l>=l1&&r<=r1)return t[node];
        int mid=l+r>>1;
        return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
} ss;
int a[500001];
ib b[500001];
vector<int> v[500003];
vector<int> v2[500003];
vector<int> v3[500003];
void setup()
{
    st1.upd(1,1,n,1,n,1);
    st2.upd(1,1,n,1,n,n);
    for(int i=1; i<n; i++)
    {
        s2=upper_bound(v[a[i]].begin(),v[a[i]].end(),i)-v[a[i]].begin();
        s2--;
        s3=v[a[i]][s2]+1;
        b[i].a=s3;
        v2[s3-1].pb(i+1);
        s2=lower_bound(v[a[i]].begin(),v[a[i]].end(),i+1)-v[a[i]].begin();
        s3=v[a[i]][s2]-1;
        b[i].b=s3;
        v3[s3+1].pb(i);
    }
}
void solve1()
{
    for(int i=0; i<n; i++)
    {
        /// di tu trai sang
        s3=b[i].b+1;
        ///i+1->s3
        for(auto x:v2[i]) ss.upd(1,1,n,x,x);
if(i==0) continue;
        if(s3==n+1)
        {
            st1.upd(1,1,n,i+1,n,i+1);
            continue;
        }
        s4=ss.get(1,1,n,i+2,s3);
        st1.upd(1,1,n,i+1,s4-1,i+1);
    }
}
void solve2()
{
    ss.reset(1,1,n);
    for(int i=n; i>=1; --i)
    {
        s3=b[i].a-1;

        for(auto x:v3[i+1]) ss.upd2(1,1,n,x,x);
         if(i>=n) continue;
        if(s3==0)
        {
            st2.upd(1,1,n,1,i,i);
            continue;
        }
        s4=ss.get2(1,1,n,s3,i);
        st2.upd(1,1,n,s4+1,i,i);
        //cout<<s4+1<<" "<<i<<" "<<s3,down
    }
}
void phongbeo()
{
    cin>>n;
    for(int i=1; i<n; i++)
        cin>>a[i],v[i].pb(0);
    v[n].pb(0);
    for(int i=1; i<=n; i++)
    {
        cin>>k;
        for(int j=1; j<=k; j++)
        {
            cin>>l;
            v[l].pb(i);
        }
    }
    for(int i=1; i<=n; i++)
        v[i].pb(n+1);
    setup();
    solve1();
    solve2();
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r;
        if(r>l)
        {
            s4=st2.get(1,1,n,l,l);
            if(s4>=r)
            {
                cout<<"YES";
            }
            else cout<<"NO";
        }
        else
        {
            s4=st1.get(1,1,n,l,l);
            if(s4<=r)
            {
                cout<<"YES";
            }
            else cout<<"NO";
        }
        cout<<"\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
long_mansion.cpp: In member function 'void IT::upd(int, int, int, int, int, int)':
long_mansion.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'int IT::get(int, int, int, int, int)':
long_mansion.cpp:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'void IT2::reset(int, int, int)':
long_mansion.cpp:98:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'void IT2::upd(int, int, int, int, int)':
long_mansion.cpp:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'void IT2::upd2(int, int, int, int, int)':
long_mansion.cpp:123:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'int IT2::get2(int, int, int, int, int)':
long_mansion.cpp:132:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'int IT2::get(int, int, int, int, int)':
long_mansion.cpp:139:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int mid=l+r>>1;
      |                 ~^~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75