Submission #752978

#	Time	Username	Problem	Language	Result	Execution time	Memory
752978		Rafi22	Seats (IOI18_seats)	C++14	100 / 100	3184 ms	118800 KiB

seats

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

vector<int>A[1000007];

const int pot=1<<20;

int seg[2*pot+7];
int lzy[2*pot+7];
int ile[2*pot+7];

void push(int v)
{
    seg[2*v]+=lzy[v];
    seg[2*v+1]+=lzy[v];
    lzy[2*v]+=lzy[v];
    lzy[2*v+1]+=lzy[v];
    lzy[v]=0;
}

void ins(int v,int a,int b,int l,int r,int x)
{
    if(a<=l&&b>=r)
    {
        seg[v]+=x;
        lzy[v]+=x;
        return ;
    }
    if(r<a||l>b) return ;
    push(v);
    ins(2*v,a,b,l,(l+r)/2,x);
    ins(2*v+1,a,b,(l+r)/2+1,r,x);
    seg[v]=min(seg[2*v],seg[2*v+1]);
    ile[v]=0;
    if(seg[v]==seg[2*v]) ile[v]+=ile[2*v];
    if(seg[v]==seg[2*v+1]) ile[v]+=ile[2*v+1];
}

void upd(int i,int j,int x)
{
    vector<int>V={A[i][j],A[i+1][j],A[i][j+1],A[i+1][j+1]};
    sort(all(V));
    ins(1,V[0],V[1]-1,1,pot,x);
    ins(1,V[2],V[3]-1,1,pot,x);
}

void S(int i,int j,int x)
{
    upd(i-1,j-1,x);
    upd(i,j-1,x);
    upd(i-1,j,x);
    upd(i,j,x);
}

vector<int>x,y;

void give_initial_chart(int h,int w,vector<int>R,vector<int>C)
{
    x=R,y=C;
    for(int i=0;i<=h+1;i++) A[i].resize(w+2,h*w+1);
    for(int i=0;i<h*w;i++) A[x[i]+1][y[i]+1]=i+1;
    for(int i=1;i<=h*w;i++) ile[i+pot-1]=1;
    for(int i=h*w+1;i<=pot;i++) seg[i+pot-1]=inf;
    for(int i=pot-1;i>0;i--)
    {
        seg[i]=min(seg[2*i],seg[2*i+1]);
        ile[i]=ile[2*i]+ile[2*i+1];
    }
    for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) upd(i,j,1);
}

int swap_seats(int a, int b)
{
    S(x[a]+1,y[a]+1,-1);
    S(x[b]+1,y[b]+1,-1);
    swap(A[x[a]+1][y[a]+1],A[x[b]+1][y[b]+1]);
    swap(x[a],x[b]);
    swap(y[a],y[b]);
    S(x[a]+1,y[a]+1,1);
    S(x[b]+1,y[b]+1,1);
    return ile[1];
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
    cout<<swap_seats(0, 5)<<endl;
    cout<<swap_seats(0, 5)<<endl;

    return 0;
}*/

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