Submission #1037279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037279		Ludissey	Seats (IOI18_seats)	C++17	17 / 100	4064 ms	146160 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;

// FIRST CEST GAUCHE DROITE LA COLLONE
//SECOND CEST HAUT BAS LE ROW

vector<vector<int>> grid;
unordered_map<int,pair<int,int>> pos;
vector<pair<pair<int,int>,pair<int,int>>> sq;
int init_cnt=0;
vector<bool> cnt;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
    grid.resize(W,vector<int>(H));
    sq.resize(W*H);
    cnt.resize(W*H);
    for (int i = 0; i < H*W; i++)
    {
        grid[C[i]][R[i]]=i;
        pos[i]={C[i],R[i]};
    }
    int mxR=0, mnL=1e9;
    int mnH=1e9, mxD=0;
    for (int i = 0; i < H*W; i++)
    {
        mxR=max(C[i],mxR);
        mxD=max(R[i],mxD);
        mnL=min(C[i],mnL);
        mnH=min(R[i],mnH);
        int sz=(mxR-mnL+1)*(mxD-mnH+1);
        if(sz<=i+1) { init_cnt++; cnt[i]=true; } 
        sq[i]={{mnL,mxR},{mnH,mxD}};
    }
}
int swap_seats(int a, int b){
    if(b<a) swap(a,b);
    pair<int,int> posA=pos[a];
    grid[pos[a].first][pos[a].second]=a;
    grid[pos[b].first][pos[b].second]=b;
    pos[a]=pos[b];
    pos[b]=posA;
    int mxR=0, mnL=1e9;
    int mnH=1e9, mxD=0;
    if(a>0){
        mnL=sq[a-1].first.first;
        mxR=sq[a-1].first.second;
        mnH=sq[a-1].second.first;
        mxD=sq[a-1].second.second;
    }

    for (int i = a; i <= b; i++)
    {
        init_cnt-=cnt[i];
        cnt[i]=0;
        mxR=max(pos[i].first,mxR);
        mxD=max(pos[i].second,mxD);
        mnL=min(pos[i].first,mnL);
        mnH=min(pos[i].second,mnH);
        int sz=(mxR-mnL+1)*(mxD-mnH+1);
        if(sz<=i+1) { init_cnt++; cnt[i]=true; } 
        sq[i]={{mnL,mxR},{mnH,mxD}};
    }
    return init_cnt;
}

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