Submission #851206

#	Time	Username	Problem	Language	Result	Execution time	Memory
851206		Pajaraja	Seats (IOI18_seats)	C++17	100 / 100	2240 ms	117144 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
int seg[4*MAXN],bag[4*MAXN],kol[4*MAXN];
vector<vector<int>> mat;
vector<int> row,col;
int h,w;
void relax(int ind)
{
    bag[2*ind]+=bag[ind];
    bag[2*ind+1]+=bag[ind];
    kol[ind]=0;
    bag[ind]=0;
}
void upd(int l,int r,int lt,int val,int ind)
{
    if(l>=lt)
    {
        bag[ind]+=val;
        return;
    }
    if(r<lt) return;
    relax(ind);
    int s=(l+r)/2;
    upd(l,s,lt,val,2*ind);
    upd(s+1,r,lt,val,2*ind+1);
    seg[ind]=min(seg[2*ind]+bag[2*ind],seg[2*ind+1]+bag[2*ind+1]);
    if(seg[ind]==seg[2*ind]+bag[2*ind]) kol[ind]+=kol[2*ind];
    if(seg[ind]==seg[2*ind+1]+bag[2*ind+1]) kol[ind]+=kol[2*ind+1];
}
void build(int l,int r,int ind)
{
    kol[ind]=r-l+1;
    if(l==r) return;
    int s=(l+r)/2;
    build(l,s,2*ind);
    build(s+1,r,2*ind+1);
}
void twobytwo(int x,int y,int what)
{
    vector<int> v;
    v.push_back(mat[x][y]); v.push_back(mat[x+1][y]); v.push_back(mat[x][y+1]);v.push_back(mat[x+1][y+1]);
    sort(v.begin(),v.end());
    for(int i=0;i<4;i++) upd(1,h*w,v[i],1-((i+what)&1)*2,1);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h=H;
    w=W;
    for(int i=0;i<h*w;i++) row.push_back(R[i]+1);
    for(int i=0;i<h*w;i++) col.push_back(C[i]+1);
    vector<int> v;
    for(int i=0;i<w+2;i++) v.push_back(MAXN);
    for(int i=0;i<h+2;i++) mat.push_back(v);
    for(int i=0;i<h*w;i++) mat[row[i]][col[i]]=i;
    build(1,h*w,1);
    for(int i=0;i<h+1;i++) for(int j=0;j<w+1;j++) twobytwo(i,j,0);
}

int swap_seats(int a, int b) {
    twobytwo(row[a],col[a],1); twobytwo(row[a]-1,col[a],1); twobytwo(row[a],col[a]-1,1); twobytwo(row[a]-1,col[a]-1,1);
    twobytwo(row[b],col[b],1); twobytwo(row[b]-1,col[b],1); twobytwo(row[b],col[b]-1,1); twobytwo(row[b]-1,col[b]-1,1);
    swap(row[a],row[b]);
    swap(col[a],col[b]);
    swap(mat[row[a]][col[a]],mat[row[b]][col[b]]);
    twobytwo(row[a],col[a],0); twobytwo(row[a]-1,col[a],0); twobytwo(row[a],col[a]-1,0); twobytwo(row[a]-1,col[a]-1,0);
    twobytwo(row[b],col[b],0); twobytwo(row[b]-1,col[b],0); twobytwo(row[b],col[b]-1,0); twobytwo(row[b]-1,col[b]-1,0);
    return kol[1];
}

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