Submission #294689

#	Time	Username	Problem	Language	Result	Execution time	Memory
294689		Autoratch	Seats (IOI18_seats)	C++14	5 / 100	4078 ms	71800 KiB

seats

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

const int N = 1 << 20;

int m,n;
vector<int> x,y;

struct node
{
    int mnx,mxx,mny,mxy;
    friend node operator+(const node &a,const node &b)
    {
        node ret;
        ret.mnx = min(a.mnx,b.mnx),ret.mxx = max(a.mxx,b.mxx);
        ret.mny = min(a.mny,b.mny),ret.mxy = max(a.mxy,b.mxy);
        return ret;
    }
}tree[N << 1];

void build(int l,int r,int idx)
{
    if(l==r) return void(tree[idx] = {x[l],x[l],y[l],y[l]});
    int m = (l+r)/2;
    build(l,m,idx*2),build(m+1,r,idx*2+1);
    tree[idx] = tree[idx*2]+tree[idx*2+1];
}

void update(int l,int r,int idx,int x,int a,int b)
{
    if(x>r or x<l) return;
    if(l==r) return void(tree[idx] = {a,a,b,b});
    int m = (l+r)/2;
    update(l,m,idx*2,x,a,b),update(m+1,r,idx*2+1,x,a,b);
    tree[idx] = tree[idx*2]+tree[idx*2+1];
}

node read(int l,int r,int idx,int x,int y)
{
    if(x>r or y<l) return {INT_MAX,INT_MIN,INT_MAX,INT_MIN};
    if(x<=l and y>=r) return tree[idx];
    int m = (l+r)/2;
    return read(l,m,idx*2,x,y)+read(m+1,r,idx*2+1,x,y);
}

void give_initial_chart(int H, int W,vector<int> R,vector<int> C) 
{
    m = H,n = W,x = R,y = C;
    build(0,m*n-1,1);
}

int swap_seats(int a,int b) 
{
    int xa = x[a],xb = x[b],ya = y[a],yb = y[b];
    update(0,m*n-1,1,a,xb,yb),update(0,m*n-1,1,b,xa,ya);
    swap(x[a],x[b]),swap(y[a],y[b]);
    int ans = 0,now = 0;
    while(now<m*n)
    {
        node rx = read(0,m*n-1,1,0,now);
        int val = (rx.mxx-rx.mnx+1)*(rx.mxy-rx.mny+1)-1;
        if(val==now) ans++,now++;
        else now = val;
    }
    return ans;
}

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