Submission #371541

#	Time	Username	Problem	Language	Result	Execution time	Memory
371541		denkendoemeer	Seats (IOI18_seats)	C++14	100 / 100	2264 ms	115548 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
#define ll long long
using namespace std;
int lazy[1<<21],b[1000005],h,w;
vector<int>r,c;
vector<vector<int>>auxi;
array<int,2>aint[1<<21];
void comb(int nod)
{
    aint[nod]={min(aint[nod*2][0],aint[nod*2+1][0])};
    aint[nod][1]=0;
    if (aint[nod*2][0]>aint[nod][0])
        aint[nod][1]+=0;
    else
        aint[nod][1]+=aint[nod*2][1];
    if (aint[nod*2+1][0]>aint[nod][0])
        aint[nod][1]+=0;
    else
        aint[nod][1]+=aint[nod*2+1][1];
}
void build(int nod=1,int st=0,int dr=h*w-1)
{
    if (st==dr){
        aint[nod]={b[st],1};
        return ;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    comb(nod);
}
void add(int nod,int x)
{
    aint[nod][0]+=x;
    lazy[nod]+=x;
}
void update(int st,int dr,int val,int nod=1,int l=0,int r=h*w-1)
{
    if (aint[1][1]==0){
        b[st]+=val;
        b[dr+1]-=val;
        return ;
    }
    if (st<=l && r<=dr){
        add(nod,val);
        return ;
    }
    int mij=(l+r)/2;
    add(2*nod,lazy[nod]);
    add(2*nod+1,lazy[nod]);
    lazy[nod]=0;
    if (st<=mij)
        update(st,dr,val,2*nod,l,mij);
    if (mij+1<=dr)
        update(st,dr,val,2*nod+1,mij+1,r);
    comb(nod);
}
void swa(int x,int y,int z)
{
    vector<int>v;
    int i,j;
    for(i=!x-1;i<(x<h);i++)
        for(j=!y-1;j<(y<w);j++)
            v.push_back(auxi[x+i][y+j]);
    sort(v.begin(),v.end());
    update(v[0],(v.size()>1?v[1]:h*w)-1,z);
    if (v.size()>2)
        update(v[2],v[3]-1,z);
}
void give_initial_chart(int h2,int w2,vector<int>r2,vector<int>c2)
{
    h=h2;
    w=w2;
    r=r2;
    c=c2;
    auxi=vector<vector<int>>(h,vector<int>(w));
    int i,j;
    for(i=0;i<h*w;i++)
        auxi[r[i]][c[i]]=i;
    for(i=0;i<=h;i++)
        for(j=0;j<=w;j++)
            swa(i,j,1);
    for(i=0;i<h*w;i++)
        b[i+1]+=b[i];
    build();
}
int swap_seats(int x,int y)
{
    int i,j,k;
    vector<array<int,2>>v;
    for(int i:{x,y})
        for(int j:{0,1})
            for(int k:{0,1})
                v.push_back({r[i]+j,c[i]+k});
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for(auto it:v)
        swa(it[0],it[1],-1);
    swap(auxi[r[x]][c[x]],auxi[r[y]][c[y]]);
    swap(r[x],r[y]);
    swap(c[x],c[y]);
    for(auto it:v)
        swa(it[0],it[1],1);
    return aint[1][1];
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:90:9: warning: unused variable 'i' [-Wunused-variable]
   90 |     int i,j,k;
      |         ^
seats.cpp:90:11: warning: unused variable 'j' [-Wunused-variable]
   90 |     int i,j,k;
      |           ^
seats.cpp:90:13: warning: unused variable 'k' [-Wunused-variable]
   90 |     int i,j,k;
      |             ^

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