Submission #1027876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027876		shenfe1	Tiles (BOI24_tiles)	C++17	0 / 100	196 ms	53328 KiB

Main

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast")

#define ll long long
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define int ll
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))

using namespace std;

const int MAX=2e5+15;
const ll inf=1e18;
const int mod=1e9+7;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}

int n,m;
int x[MAX],y[MAX];
vector<pii> vec[MAX];

struct node{
    bool is[2];
    int t,add;

    node(){
        is[0]=is[1]=1;
        add=-1;
        t=0;
    }
};

struct segtree{

    node t[4*MAX];

    void upd(int v,int tl,int tr,int x){
        t[v].is[x%2]=1;
        t[v].is[1-x%2]=0;
        t[v].add=x;
        t[v].t=(tr-tl+1)*x;
    }

    void push(int v,int tl,int tr){
        if(t[v].add!=-1){
            int tm=(tl+tr)/2;
            upd(2*v,tl,tm,t[v].add);
            upd(2*v+1,tm+1,tr,t[v].add);
            t[v].add=-1;
        }
    }

    node mrg(node a,node b){
        node res;
        res.t=a.t+b.t;
        res.is[0]=(a.is[0]&b.is[0]);
        res.is[1]=(a.is[1]&&b.is[1]);
        return res;
    }

    void update(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            upd(v,tl,tr,x);
            return;
        }
        int tm=(tl+tr)/2;
        push(v,tl,tr);
        update(2*v,tl,tm,l,r,x);
        update(2*v+1,tm+1,tr,l,r,x);
        t[v]=mrg(t[2*v],t[2*v+1]);
    }

    node get(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return node();
        if(l<=tl&&tr<=r){
            return t[v];
        }
        int tm=(tl+tr)/2;
        push(v,tl,tr);
        return mrg(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
    }
}T;

int rev[8*MAX];

void solve(){
    cin>>n>>m;
    set<int> stx,sty;
    map<int,int> mpx,mpy;
    int cur=0;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        y[i]/=2;
        sty.in(y[i]);
        // if(y[i]!=0)sty.in(y[i]-1);
        stx.in(x[i]);
    }
    for(int x:sty){
        if(cur%2!=x%2)cur++;
        mpy[x]=cur++;
    }
    for(int i=1;i<=n;i++){
        y[i]=mpy[y[i]];
    }
    cur=0;
    for(int x:stx){
        if(cur%2!=x%2)cur++;
        mpx[x]=cur++;
    }
    for(int i=1;i<=n;i++){
        // cout<<x[i]<<" "<<mpx[x[i]]<<"\n";
        rev[mpx[x[i]]]=x[i];
        x[i]=mpx[x[i]];

        
        // cout<<x[i]
    }
    for(int i=1;i<=n;i++){
        // cout<<x[i]<<" "<<y[i]<<"\n";
        int nx=x[i%n+1],ny=y[i%n+1];
        if(nx==x[i]){
            vec[x[i]].pb({min(ny,y[i]),max(ny,y[i])-1});
        }
    }
    int ans=0;
    for(int i=0;i<cur;i++){
        for(auto [l,r]:vec[i]){
            if(T.get(1,0,sz(sty)-1,l,r).t==0){
                // cout<<l<<" "<<r<<" "<<i+1<<"\n";
                T.update(1,0,sz(sty)-1,l,r,i+1);
                // cout<<T.get(1,0,sz(sty)-1,0,sz(sty)-1).t<<"\n";
            }
            else{
                // cout<<l<<" "<<r<<" "<<i+1<<"\n";
                node x=T.get(1,0,sz(sty)-1,l,r);
                if(x.is[1-i%2]){
                    T.update(1,0,sz(sty)-1,l,r,0);
                }
                else{
                    cout<<ans<<"\n";
                    return;
                }
            }
            // assert(sum==0||sum==r-l+1);
        }
        if(T.t[1].is[1-i%2]){
            // cout<<i<<" "<<rev[i]<<"\n";
            if(rev[i+1]==0){
                ans=max(ans,rev[i+2]);
            }
            else{
                ans=max(ans,rev[i+1]);
            }
        }
        // assert(ans<=m);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}   

• Subtask 1: 0 / 4
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10