Submission #198127

#	Time	Username	Problem	Language	Result	Execution time	Memory
198127		hank55663	Seats (IOI18_seats)	C++14	100 / 100	2574 ms	176608 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
    node *l,*r;
    int Min,Minnum;
    int a,b;
    int tag;
    node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){

    }
}*root;
int Min(node *n){
    return n->Min+n->tag;
}
void pull(node *n){
    if(Min(n->l)==Min(n->r)){
        n->Min=Min(n->l);
        n->Minnum=n->l->Minnum+n->r->Minnum;
    }
    else if(Min(n->l)>Min(n->r)){
        n->Min=Min(n->r);
        n->Minnum=n->r->Minnum;
    }
    else{
        n->Min=Min(n->l);
        n->Minnum=n->l->Minnum;
    }
}
void push(node *n){
    n->l->tag+=n->tag;
    n->r->tag+=n->tag;
    n->tag=0;
}
void build(node *n,int *a){
    if(n->a==n->b){
      n->Min=a[n->a];
      return;
    }
    int mid=(n->a+n->b)/2;
    n->l=new node(n->a,mid);
    n->r=new node(mid+1,n->b);
    build(n->l,a);
    build(n->r,a);
    pull(n);
}
void add(node *n,int l,int r,int k){
    if(l>r)return;
   // if(n==root){
    //   printf("%d %d %d\n",l,r,k);
   // }
    if(n->a>=l&&n->b<=r){
        n->tag+=k;
        return;
    }
    if(n->b<l||n->a>r)return;
    push(n);
    add(n->l,l,r,k);
    add(n->r,l,r,k);
    pull(n);
}
int query(node *n,int l,int r){
    if(l>r)return 0;
    if(n->a>=l&&n->b<=r){
   //     printf("%d %d %d %d %d\n",Min(n),n->a,n->b,n->tag,n->Min);
        assert(Min(n)>=4);
        if(Min(n)==4)return n->Minnum;
        else return 0;
    }
    if(n->b<l||n->a>r)return 0;
    push(n);
    int x=query(n->l,l,r)+query(n->r,l,r);
    pull(n);
    return x;
}
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
#define mp make_pair
pii p[1000005];
vector<vector<int> > v;
int X[4]={0,0,1,1};
int Y[4]={0,1,0,1};
int len;
int a[1000005];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  v.resize(H+2,vector<int>(W+2,H*W));
  for(int i = 0;i<H*W;i++){
    //printf("%d %d %d %d\n",H,W,R[i]+1,C[i]+1);
    p[i]=mp(R[i]+1,C[i]+1);
    //printf("%d %d %d\n",v[R[i]+1][C[i]+1],R[i],C[i]);
  //  assert(v[R[i]+1][C[i]+1]==1e9);
    v[R[i]+1][C[i]+1]=i;
  }
  len=H*W-1;
  root=  new node(0,H*W-1);
  //build(root);
  for(int i =0;i<=H;i++){
    for(int j=0;j<=W;j++){
      int tmp[4];
      for(int k =0;k<4;k++){
        tmp[k]=v[i+X[k]][j+Y[k]];
      }
      sort(tmp,tmp+4);
      a[tmp[0]]++;
      a[tmp[1]]--;
      a[tmp[2]]++;
      a[tmp[3]]--;
      //add(root,tmp[0],tmp[1]-1,1);
      //add(root,tmp[1],len,-1);
     // add(root,tmp[2],tmp[3]-1,1);
     // add(root,tmp[3],len,-1);
    }
  }
  for(int i = 1;i<=H*W;i++)a[i]+=a[i-1];
  build(root,a);
}
int swap_seats(int a, int b) {
 // printf("%d %d\n",a,b);
  for(int t=0;t<2;t++){
    for(int i=p[a].x-1;i<=p[a].x;i++){
      for(int j=p[a].y-1;j<=p[a].y;j++){
        int tmp[4];
        for(int k=0;k<4;k++){
          tmp[k]=v[i+X[k]][j+Y[k]];
        }
        sort(tmp,tmp+4);
        add(root,tmp[0],tmp[1]-1,-1);
       // add(root,tmp[1],len,1);
        add(root,tmp[2],tmp[3]-1,-1);
        //add(root,tmp[3],len,1);
      }
    }
    swap(a,b);
  }
  swap(p[a],p[b]);
  v[p[a].x][p[a].y]=a;
  v[p[b].x][p[b].y]=b;
  for(int t=0;t<2;t++){
    for(int i=p[a].x-1;i<=p[a].x;i++){
      for(int j=p[a].y-1;j<=p[a].y;j++){
        int tmp[4];
        for(int k=0;k<4;k++){
          tmp[k]=v[i+X[k]][j+Y[k]];
        }
        sort(tmp,tmp+4);
        add(root,tmp[0],tmp[1]-1,1);
        //add(root,tmp[1],len,-1);
        add(root,tmp[2],tmp[3]-1,1);
        //add(root,tmp[3],len,-1);
      }
    }
    swap(a,b);
  }
 // printf("%d\n",query(root,0,len));
  return query(root,0,len);
}

Compilation message (stderr)

seats.cpp: In constructor 'node::node(int, int)':
seats.cpp:7:11: warning: 'node::b' will be initialized after [-Wreorder]
     int a,b;
           ^
seats.cpp:6:9: warning:   'int node::Min' [-Wreorder]
     int Min,Minnum;
         ^~~
seats.cpp:9:5: warning:   when initialized here [-Wreorder]
     node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){
     ^~~~
seats.cpp:8:9: warning: 'node::tag' will be initialized after [-Wreorder]
     int tag;
         ^~~
seats.cpp:5:11: warning:   'node* node::l' [-Wreorder]
     node *l,*r;
           ^
seats.cpp:9:5: warning:   when initialized here [-Wreorder]
     node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){
     ^~~~

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