Submission #362277

#	Time	Username	Problem	Language	Result	Execution time	Memory
362277		Fysty	Seats (IOI18_seats)	C++17	70 / 100	4027 ms	141804 KiB

seats

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int INF=1e9;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define X F
#define Y S
struct node
{
    int mn,cnt,tag;
    node(): mn(INF),cnt(1),tag(0){}
    node operator+(const node &a)
    {
        node rt;
        if(a.mn<mn) rt.mn=a.mn,rt.cnt=a.cnt;
        else if(a.mn>mn) rt.mn=mn,rt.cnt=cnt;
        else rt.mn=mn,rt.cnt=a.cnt+cnt;
        rt.tag=0;
        return rt;
    }
}st[N<<2];
vector<vector<int> > p;
pair<int,int> seat[N];
int dx[4]={0,0,-1,-1},dy[4]={0,-1,0,-1};
int sz;
void give_tag(int t,int id)
{
    st[id].tag+=t;
    if(st[id].mn==INF) st[id].mn=t;
    else st[id].mn+=t;
}
void tag_down(int id)
{
    give_tag(st[id].tag,id<<1);
    give_tag(st[id].tag,id<<1|1);
    st[id].tag=0;
}
void build(int l,int r,int id)
{
    if(l==r) st[id]=node();
    else
    {
        int mid=l+r>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
        st[id]=st[id<<1]+st[id<<1|1];
    }
}
void modify(int l,int r,int ql,int qr,int t,int id)
{
    if(ql<=l&&r<=qr)
    {
        give_tag(t,id);
        return;
    }
    if(l!=r) tag_down(id);
    int mid=l+r>>1;
    if(ql<=mid) modify(l,mid,ql,qr,t,id<<1);
    if(qr>mid) modify(mid+1,r,ql,qr,t,id<<1|1);
    st[id]=st[id<<1]+st[id<<1|1];
}
void calc(int x,int y,int t)
{
    //cout<<"begin calc("<<x<<" "<<y<<" "<<t<<")\n";
    int tmp[4]={p[x][y],p[x+1][y],p[x][y+1],p[x+1][y+1]};
    sort(tmp,tmp+4);
    if(tmp[0]!=tmp[1])
    {
        //cout<<"modifying tmp[0] tmp[1]-1: "<<tmp[0]<<" "<<tmp[1]-1<<"\n";
        modify(1,sz,tmp[0],tmp[1]-1,t,1);
        //cout<<"modify tmp[0] tmp[1]-1 done: "<<tmp[0]<<" "<<tmp[1]-1<<"\n";
    }
    if(tmp[2]!=tmp[3])
    {
        //cout<<"modifying tmp[2] tmp[3]-1: "<<tmp[2]<<" "<<tmp[3]-1<<"\n";
        modify(1,sz,tmp[2],tmp[3]-1,t,1);
        //cout<<"modify tmp[2] tmp[3]-1 done: "<<tmp[2]<<" "<<tmp[3]-1<<"\n";
    }
    //cout<<"end calc("<<x<<" "<<y<<" "<<t<<")\n";
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
    sz=H*W;
    p.resize(H+2,vector<int>(W+2,sz+1));
    rep(i,sz)
    {
        p[R[i]+1][C[i]+1]=i+1;
        seat[i+1]={R[i]+1,C[i]+1};
    }
    //cout<<"p and seat setup done\n";
    build(1,sz,1);
    //cout<<"build done\n";
    rep(i,H+1) rep(j,W+1)
    {
        calc(i,j,1);
        //cout<<"init "<<i<<" "<<j<<" done\n";
    }
    //cout<<st[1].cnt<<"\n\n";
}
int swap_seats(int a,int b)
{
    a++,b++;
    //cout<<"seat[a]: "<<seat[a].F<<" "<<seat[a].S<<"\n";
    rep(i,4) calc(seat[a].F+dx[i],seat[a].S+dy[i],-1);
    p[seat[a].F][seat[a].S]=b;
    rep(i,4) calc(seat[a].F+dx[i],seat[a].S+dy[i],1);
    //cout<<"a done\n\n";
    //cout<<"seat[b]: "<<seat[b].F<<" "<<seat[b].S<<"\n";
    rep(i,4) calc(seat[b].F+dx[i],seat[b].S+dy[i],-1);
    p[seat[b].F][seat[b].S]=a;
    rep(i,4) calc(seat[b].F+dx[i],seat[b].S+dy[i],1);
    //cout<<"b done\n\n";
    swap(seat[a],seat[b]);
    return st[1].cnt;
}
/*
int main()
{
    int h,w;
    cin>>h>>w;
    vector<int> r(h*w),c(h*w);
    rep(i,h*w) cin>>r[i];
    rep(i,h*w) cin>>c[i];
    give_initial_chart(h,w,r,c);
    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        cout<<swap_seats(a,b)<<"\n";
    }
}
*/

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid=l+r>>1;
      |                 ~^~
seats.cpp: In function 'void modify(int, int, int, int, int, int)':
seats.cpp:60:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid=l+r>>1;
      |             ~^~

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