Submission #176090

#	Time	Username	Problem	Language	Result	Execution time	Memory
176090		kishtarn555	Seats (IOI18_seats)	C++14	11 / 100	4101 ms	130168 KiB

seats

#include "seats.h"
#include <iostream>
#include <algorithm>
using namespace std;
#define ind(a,b) ((a)*(WW+2)+b)
int mat[4000000];

vector<int> r;
vector<int> c;
int HH,WW;

struct st {
    st *l, *r;
    int m,f;
    int M,F;
    int lz1,lz2;
};


st *bl,*wt;

st* build (int l, int r) {
    st * n = new st;
    n->lz1=0;
    n->lz2=0;
    n->m=0;
    n->f=1;
    n->M=0;
    n->F=1;
    n->l=n->r=NULL;
    if (l==r)
        return n;
    n->l = build(l, (l+r)/2);
    n->r = build((l+r)/2+1,r);
    n->f = n->l->f+ n->r->f;
    n->F = n->l->F+ n->r->F;
    return n;
}
int tmp[4];
void push(st *cur) {
    cur->m+=cur->lz1;
    cur->M+=cur->lz2;
    if (cur->l) {
        cur->l->lz1+=cur->lz1;
        cur->l->lz2+=cur->lz2;
        cur->r->lz1+=cur->lz1;
        cur->r->lz2+=cur->lz2;

    }
    cur->lz1=0;
    cur->lz2=0;
}
void update (st * cur, int l,int r, const int i,const  int j,const int v1,const int v2) {
    push(cur);
    if (j < l || r < i)
        return;
    if (i<=l && r<=j) {
        cur->lz1+=v1;
        cur->lz2+=v2;
        push(cur);
        return;
    }
    int m =(l+r)/2;
    update(cur->l, l,m, i,j,v1,v2);
    update(cur->r, m+1,r, i,j,v1,v2);

    if (cur->l->M < cur->r->M) {
        cur->M=cur->l->M;
        cur->F=cur->l->F;
        cur->m=cur->l->m;
        cur->f=cur->l->f;
    }else if (cur->l->M > cur->r->M) {
        cur->M=cur->r->M;
        cur->F=cur->r->F;
        cur->m=cur->r->m;
        cur->f=cur->r->f;
    }else {
        if (cur->l->m < cur->r->m) {
            cur->M=cur->l->M;
            cur->F=cur->l->F;
            cur->m=cur->l->m;
            cur->f=cur->l->f;
        } else if (cur->l->m > cur->r->m) {
            cur->M=cur->r->M;
            cur->F=cur->r->F;
            cur->m=cur->r->m;
            cur->f=cur->r->f;

        }    else {
            cur->M=cur->r->M;
            cur->F=cur->r->F+cur->l->F;
            cur->m=cur->r->m;
            cur->f=cur->r->f+cur->l->f;


        }
    }


}


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    HH=H;
    WW=W;
    r=R;
    c=C;
  for (int i =0; i < H+2; i++) {
    for (int j =0; j<  W+2; j++)
        mat[ind(i,j)]=H*W;
  }

  for (int i =0; i < H*W; i++) {
    mat[ ind(R[i]+1 ,C[i]+1)]=i;
  }

  bl=build(0,H*W-1);
  for (int i =1; i < H+2; i++) {
    for (int j =1; j < W+2; j++) {
        tmp[0]=mat[ind(i-1,j-1)];
        tmp[1]=mat[ind(i-1,j)];
        tmp[2]=mat[ind(i,j-1)];
        tmp[3]=mat[ind(i,j)];
        sort(tmp,tmp+4);
//        cout << mat[i][j]<<"::"<<tmp[0]<<","<<tmp[1]<<","<<tmp[2]<<","<<tmp[3]<<","<<tmp[4]<<endl;
        int ind=2;
        if (tmp[2]==H*W)ind=1;
        if (tmp[1]==H*W)ind=0;
//        cout << tmp[0]<<","<<tmp[1]-1<<";1 pintado"<<endl;
//        if (ind==2)
        update(bl, 0, H*W-1, tmp[0],tmp[1]-1,1,0);
        if (ind == 2){
//        cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
        update(bl, 0, H*W-1, tmp[ind],tmp[ind+1]-1,0,1);
        }
    }
  }
//  for (int i =0; i <)
//    cout <<"{"<< bl->m <<","<<bl->f<<"}"<<"{"<<bl->M<<","<<bl->F <<"}";
//    cout << endl;
//    cout << endl;
}

int swap_seats(int a, int b) {

    int r1=r[a]+1,c1=c[a]+1;
    int r2=r[b]+1,c2=c[b]+1;
//    cout <<"______________"<<endl;
//    cout << r1 << ","<<c1<<endl;
//    cout << r2 << ","<<c2<<endl;
    swap(r[a],r[b]);
    swap(c[a],c[b]);

    for (int i =0; i < 2; i++){
        for (int j = 0; j < 2; j++) {
            tmp[0]=mat[ind(i+r1-1,j+c1-1)];
            tmp[1]=mat[ind(i+r1-1,j+c1)];
            tmp[2]=mat[ind(i+r1,j+c1-1)];
            tmp[3]=mat[ind(i+r1,j+c1)];
            sort(tmp,tmp+4);
            int ind=2;
            if (tmp[2]==HH*WW)ind=1;
            if (tmp[1]==HH*WW)ind=0;
            update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,-1,0);
            if (ind == 2){
//            cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
            update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,-1);
            }
        }
    }

    for (int i =0; i < 2; i++){
        for (int j = 0; j < 2; j++) {
            tmp[0]=mat[ind(i+r2-1,j+c2-1)];
            tmp[1]=mat[ind(i+r2-1,j+c2)];
            tmp[2]=mat[ind(i+r2,j+c2-1)];
            tmp[3]=mat[ind(i+r2,j+c2)];
            sort(tmp,tmp+4);
            int ind=2;
            if (tmp[2]==HH*WW)ind=1;
            if (tmp[1]==HH*WW)ind=0;
            update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,-1,0);
            if (ind == 2){
//            cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
            update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,-1);
            }
        }
    }
    swap(mat[ind(r1,c1)] ,mat[ind(r2,c2)]);

    for (int i =0; i < 2; i++){
        for (int j = 0; j < 2; j++) {
            tmp[0]=mat[ind(i+r1-1,j+c1-1)];
            tmp[1]=mat[ind(i+r1-1,j+c1)];
            tmp[2]=mat[ind(i+r1,j+c1-1)];
            tmp[3]=mat[ind(i+r1,j+c1)];
            sort(tmp,tmp+4);
            int ind=2;
            if (tmp[2]==HH*WW)ind=1;
            if (tmp[1]==HH*WW)ind=0;
            update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,1,0);
            if (ind == 2){
//            cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
            update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,1);
            }
        }
    }
    for (int i =0; i < 2; i++){
        for (int j = 0; j < 2; j++) {
            tmp[0]=mat[ind(i+r2-1,j+c2-1)];
            tmp[1]=mat[ind(i+r2-1,j+c2)];
            tmp[2]=mat[ind(i+r2,j+c2-1)];
            tmp[3]=mat[ind(i+r2,j+c2)];
            sort(tmp,tmp+4);;
            int ind=2;
            if (tmp[2]==HH*WW)ind=1;
            if (tmp[1]==HH*WW)ind=0;
            update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,1,0);
            if (ind == 2){
//            cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
            update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,1);
            }
        }
    }
    int t =0;
    if (bl->M ==0 && bl->m == 4) {
        t= bl->f;
    }
    return t;

}

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