Submission #1037277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037277		Ludissey	Seats (IOI18_seats)	C++17	0 / 100	4029 ms	94440 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;

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(H,vector<int>(W));
    sq.resize(W*H);
    cnt.resize(W*H);
    for (int i = 0; i < H*W; i++)
    {
        grid[R[i]][C[i]]=i;
        pos[i]={R[i],C[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){
        mxR=sq[a].first.first;
        mnL=sq[a].first.second;
        mnH=sq[a].second.first;
        mxD=sq[a].second.second;
    }

    for (int i = a; i <= b; i++)
    {
        init_cnt-=cnt[i];
        cnt[i]=0;
        mxR=max(pos[i].second,mxR);
        mxD=max(pos[i].first,mxD);
        mnL=min(pos[i].second,mnL);
        mnH=min(pos[i].first,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: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30