Submission #828444

#	Time	Username	Problem	Language	Result	Execution time	Memory
828444		vnm06	Seats (IOI18_seats)	C++14	37 / 100	4091 ms	76648 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"

using namespace std;


int n;
int h, w;
int pos[1000005][2];
int mi_tree[4000005][2];
int ma_tree[4000005][2];

void update(int v, int le, int ri, int id)
{
    if(ri<id || le>id) return;
    if(le==ri)
    {
        mi_tree[v][0]=pos[le][0];
        mi_tree[v][1]=pos[le][1];
        ma_tree[v][0]=pos[le][0];
        ma_tree[v][1]=pos[le][1];
    }
    else
    {
        int mid=(le+ri)/2;
        update(2*v, le, mid, id);
        update(2*v+1, mid+1, ri, id);
        mi_tree[v][0]=min(mi_tree[2*v][0], mi_tree[2*v+1][0]);
        mi_tree[v][1]=min(mi_tree[2*v][1], mi_tree[2*v+1][1]);
        ma_tree[v][0]=max(ma_tree[2*v][0], ma_tree[2*v+1][0]);
        ma_tree[v][1]=max(ma_tree[2*v][1], ma_tree[2*v+1][1]);

    }
}

pair<pair<int, int>, pair<int, int> > query(int v, int le, int ri, int be, int en)
{
    if(le>en || ri<be) return {{1e9, 0}, {1e9, 0}};
    if(be<=le && ri<=en) return {{mi_tree[v][0], ma_tree[v][0]}, {mi_tree[v][1], ma_tree[v][1]}};
    else
    {
        int mid=(le+ri)/2;
        pair<pair<int, int>, pair<int, int> > pr1=query(2*v, le, mid, be, en), pr2=query(2*v+1, mid+1, ri, be, en);
        return {{min(pr1.first.first, pr2.first.first), max(pr1.first.second, pr2.first.second)}, {min(pr1.second.first, pr2.second.first), max(pr1.second.second, pr2.second.second)}};
    }
}

int br=0;

int ans[1000005];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    h=H;
    w=W;
    n=h*w;
    for(int i=0; i<n; i++) pos[i][0]=R[i], pos[i][1]=C[i];
    for(int i=0; i<n; i++) update(1, 0, n-1, i);
    for(int i=0; i<n; i++)
    {
        pair<pair<int, int>, pair<int, int> > pr=query(1, 0, n-1, 0, i);
        int t=(pr.first.second-pr.first.first+1)*(pr.second.second-pr.second.first+1);
        if(t==i+1) {ans[i]=1; br++;}
    }
}

int swap_seats(int a, int b)
{
    if(a>b) swap(a, b);
    swap(pos[a][0], pos[b][0]);
    swap(pos[a][1], pos[b][1]);
    update(1, 0, n-1, a);
    update(1, 0, n-1, b);
    int mt=0;
    for(int i=a; i<b; i++)
    {
        br-=ans[i];
        ans[i]=0;
        if(i<mt-1) continue;
        pair<pair<int, int>, pair<int, int> > pr=query(1, 0, n-1, 0, i);
        int t=(pr.first.second-pr.first.first+1)*(pr.second.second-pr.second.first+1);
        if(t==i+1) {ans[i]=1; br++;}
        if(t>mt) mt=t;
    }
    return br;
}

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