Submission #362290

#	Time	Username	Problem	Language	Result	Execution time	Memory
362290		Fysty	Seats (IOI18_seats)	C++17	100 / 100	2166 ms	110792 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 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,tags[N];
bool cur=0;
void give_tag(int t,int id)
{
    st[id].tag+=t;
    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].mn=tags[l];
        st[id].cnt=1;
        st[id].tag=0;
    }
    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 update(int x,int y,int t)
{
    if(x==y) return;
    if(!cur)
    {
        tags[x]+=t;
        tags[y]-=t;
    }
    else modify(1,sz,x,y-1,t,1);
}
void calc(int x,int y,int t)
{
    int tmp[4]={p[x][y],p[x+1][y],p[x][y+1],p[x+1][y+1]};
    sort(tmp,tmp+4);
    update(tmp[0],tmp[1],t);
    update(tmp[2],tmp[3],t);
}
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};
    }
    rep(i,H+1) rep(j,W+1) calc(i,j,1);
    rep1(i,sz) tags[i]+=tags[i-1];
    build(1,sz,1);
    cur=1;
}
int swap_seats(int a,int b)
{
    a++,b++;
    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);
    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);
    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:50:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int mid=l+r>>1;
      |                 ~^~
seats.cpp: In function 'void modify(int, int, int, int, int, int)':
seats.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     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: 30 / 30