Submission #138220

#	Time	Username	Problem	Language	Result	Execution time	Memory
138220		degelo	Seats (IOI18_seats)	C++17	17 / 100	4062 ms	59544 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
#define maxn 1000006
using namespace std;
int tot=1;
struct conjunto{
    int minr,minc,maxr,maxc;
    bool beuaty;
};
struct peca{
    int r,c;
};
conjunto grupo[maxn];
peca pes[maxn];
void give_initial_chart(int n,int m,vector<int> row,vector<int> column){
    for(int i=0;i<n*m;i++){
        pes[i].r=row[i];pes[i].c=column[i];
    }
    grupo[0].minr=pes[0].r;
    grupo[0].maxr=pes[0].r;
    grupo[0].maxc=pes[0].c;
    grupo[0].minc=pes[0].c;
    grupo[0].beuaty=true;
    for(int i=1;i<n*m;i++){
        grupo[i].minr=min(grupo[i-1].minr,pes[i].r);
        grupo[i].maxr=max(grupo[i-1].maxr,pes[i].r);
        grupo[i].minc=min(grupo[i-1].minc,pes[i].c);
        grupo[i].maxc=max(grupo[i-1].maxc,pes[i].c);
        if((grupo[i].maxr-grupo[i].minr+1)*(grupo[i].maxc-grupo[i].minc+1)==i+1){
            grupo[i].beuaty=true;
            tot++;
        }
    }
}
int swap_seats(int a,int b){
    if(a>b) swap(a,b);
    swap(pes[a].r,pes[b].r);
    swap(pes[a].c,pes[b].c);
    if(a==0){
        a++;
        grupo[0].minr=pes[0].r;
        grupo[0].maxr=pes[0].r;
        grupo[0].maxc=pes[0].c;
        grupo[0].minc=pes[0].c;
        grupo[0].beuaty=true;
    }
    for(int i=a;i<b;i++){
        if(grupo[i].beuaty) tot--;
        grupo[i].beuaty=false;
        grupo[i].minr=min(grupo[i-1].minr,pes[i].r);
        grupo[i].maxr=max(grupo[i-1].maxr,pes[i].r);
        grupo[i].minc=min(grupo[i-1].minc,pes[i].c);
        grupo[i].maxc=max(grupo[i-1].maxc,pes[i].c);
        if((grupo[i].maxr-grupo[i].minr+1)*(grupo[i].maxc-grupo[i].minc+1)==i+1){
            grupo[i].beuaty=true;
            tot++;
        }
    }
    return tot;
}

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