Submission #1038705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038705		boyliguanhan	Seats (IOI18_seats)	C++17	100 / 100	2372 ms	136136 KiB

seats

#include "seats.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
void operator+=(pair<int,int>&a,pair<int,int>b){
    a.first+=b.first,a.second+=b.second;
}
struct segtree{
    struct DDT{
        pair<int,int>mn,lz;
        int mnc,l,r;
        DDT(){mnc=1,mn=lz={0,0};}
        DDT(DDT a,DDT b){
            *this=a;
            if(b.mn<mn)
                mn=b.mn,mnc=0;
            if(b.mn==mn)
                mnc+=b.mnc;
        }
    } T[1<<21];
    void pd(int i){
        pair<int,int>k=T[i].lz;
        if(k.first||k.second){
            T[i].lz={0,0},
            T[i].mn+=k;
            if(i<1<<20)
                T[i*2].lz+=k,
                T[i*2+1].lz+=k;
        }
    }
    void upd(int i,int l,int r,int ll,int rr,pair<int,int> v){
        T[i].l=l,T[i].r=r;
        pd(i);if(ll<=l&&r<=rr)
            return T[i].lz=v,pd(i);
        if(ll>r||l>rr) return;
        upd(i*2,l,l+r>>1,ll,rr,v);
        upd(i*2+1,l+r+2>>1,r,ll,rr,v);
        T[i]=DDT(T[i*2],T[i*2+1]);
    }
} ST;
vector<int>c,r;
vector<vector<int>>app;
int CN;
bitset<1000100>had;
inline void dostuf(int x,int y,int l,int r,int coef){
    vector<int>v;
    for(int i=0;i<2;i++) for(int j=0;j<2;j++)
        v.push_back(min(r,max(l,app[x+i][y+j])));
    sort(v.begin(),v.end());
    ST.upd(1,1,CN,v[0],v[1]-1,{coef,0});
    ST.upd(1,1,CN,v[2],v[3]-1,{0,coef});
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    CN=H*W;
    app.resize(H+2,vector<int>(W+2,1e9));
    for(auto&i:C)i++;
    for(auto&i:R)i++;
    C.insert(C.begin(),0);
    R.insert(R.begin(),0);
    c=C;r=R;
    for(int i=1;i<=H*W;i++)
        app[R[i]][C[i]]=i;
    for(int i=0;i<=H;i++)
        for(int j=0;j<=W;j++)
            dostuf(i,j,1,CN+1,1);
}
set<pair<int,int>>S;
inline void do_contrib(int l,int r,int coef){
    for(auto [i,j]:S)
        dostuf(i,j,l,r,coef);
}
int swap_seats(int a, int b) {
    a++;b++; if(a>b)swap(a,b);
    S.clear();
    for(int i=0;i<2;i++) for(int j=0;j<2;j++)
        S.insert({r[a]-i,c[a]-j}),S.insert({r[b]-i,c[b]-j});
    do_contrib(a,b,-1);
    swap(c[a],c[b]);
    swap(r[a],r[b]);
    app[r[a]][c[a]]=a;
    app[r[b]][c[b]]=b;
    do_contrib(a,b,1);
    return ST.T[1].mnc;
}

Compilation message (stderr)

seats.cpp: In member function 'void segtree::upd(int, int, int, int, int, std::pair<int, int>)':
seats.cpp:36:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         upd(i*2,l,l+r>>1,ll,rr,v);
      |                   ~^~
seats.cpp:37:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         upd(i*2+1,l+r+2>>1,r,ll,rr,v);
      |                   ~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30