Submission #800272

#	Time	Username	Problem	Language	Result	Execution time	Memory
800272		gagik_2007	Seats (IOI18_seats)	C++17	17 / 100	4067 ms	59308 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
ll n,m,k;
vector<int>r,c;
ll sum=0;
vector<int>corr;
vector<int>ci1,ci2,cj1,cj2;

void update_corr(int a, int b){
    int i1,i2,j1,j2;
    if(a!=0){
        i1=ci1[a-1];
        i2=ci2[a-1];
        j1=cj1[a-1];
        j2=cj2[a-1];
    }
    else{
        i1=i2=r[a];
        j1=j2=c[a];
    }
    for(int i=a;i<b;i++){
        if(i1>r[i])i1=r[i];
        if(i2<r[i])i2=r[i];
        if(j1>c[i])j1=c[i];
        if(j2<c[i])j2=c[i];
        // cout<<i<<": "<<i1<<" "<<i2<<" "<<j1<<" "<<j2<<endl;
        bool rgh=false;
        if((j2-j1+1)*(i2-i1+1)==i+1){
            rgh=true;
        }
        if(rgh&&!corr[i])sum++;
        else if(!rgh&&corr[i])sum--;
        corr[i]=rgh;
        ci1[i]=i1;
        ci2[i]=i2;
        cj1[i]=j1;
        cj2[i]=j2;
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    r=R;
    c=C;
    n=H;
    m=W;
    corr.resize(n*m,0);
    ci1.resize(n*m,0);
    ci2.resize(n*m,0);
    cj1.resize(n*m,0);
    cj2.resize(n*m,0);
    update_corr(0,n*m);
}

int swap_seats(int a, int b) {
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    update_corr(min(a,b),max(a,b));
    return sum;
}

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