Submission #1042924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042924		Itamar	Seats (IOI18_seats)	C++14	33 / 100	954 ms	134996 KiB

seats

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

const int siz = 1e6+2;
int p[siz];
int v[siz];
int N;
struct node{
  int l,r,mid,maxi,cam,pl; // num of elements equal to maxi
  node* sl = NULL,*sr;
  node(int li, int ri){
    l = li, r = ri, mid = (l+r)/2, maxi = 0,cam=0,pl=0;
    if(l<r){
      sl = new node(l,mid);
      sr = new node(mid+1,r);
    }else if(l > 0 && l <= N)cam = 1;
  }
  void push(){
      if(sl == NULL)return;
      sl->maxi+=pl;
      sr->maxi+=pl;
      sr->pl+=pl;
      sl->pl+=pl;
      pl=0;
  }
  void update(int a, int b, int val){
      if(a > r || b < l)return;
      push();
      if(a <= l && b>=r){
          maxi+=val;
          pl += val;
      }else{
          sl->update(a,b,val);
          sr->update(a,b,val);
          if(sl->maxi > sr->maxi)cam = sl->cam;
          else if(sl->maxi < sr->maxi)cam = sr->cam;
          else cam = sl->cam+sr->cam;
          maxi = max(sl->maxi,sr->maxi);
      }
  }
};
node* seg;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    N=W;
    p[0]=N+1;
    p[N+1]=N+1;
    seg = new node(1,N);
    for(int i = 0; i <W; i++)p[C[i]+1]=i+1;
    for(int i = 0; i < N; i++)v[i+1] = C[i]+1;
    for(int i = 1; i < N; i++){
        seg->update(max(p[i],p[i+1]),N,1);
    }
    for(int i = 1; i <= N; i++)seg->update(i,N,-1);
}

int swap_seats(int a, int b) {
   a++,b++;
    seg->update(max(p[v[a]],p[v[a]+1]),1e6,-1);
    seg->update(max(p[v[a]],p[v[a]-1]),1e6,-1);

    seg->update(max(p[v[b]],p[v[b]+1]),1e6,-1);
    seg->update(max(p[v[b]],p[v[b]-1]),1e6,-1);

    swap(p[v[a]],p[v[b]]);
    seg->update(max(p[v[a]],p[v[a]+1]),1e6,1);
    seg->update(max(p[v[a]],p[v[a]-1]),1e6,1);

    seg->update(max(p[v[b]],p[v[b]+1]),1e6,1);
    seg->update(max(p[v[b]],p[v[b]-1]),1e6,1);
    
    swap(v[a],v[b]);
    return seg->cam;
}

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