Submission #1014980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014980		hyakup	Seats (IOI18_seats)	C++17	37 / 100	4029 ms	122960 KiB

seats

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

const int maxn = 1e6 + 10;

vector<int> linha1(maxn, maxn), linha2(maxn, -maxn), coluna1(maxn, maxn), coluna2(maxn, -maxn), marc(maxn);
vector<int> i, j;
int n, m;
int resp; 

struct Node{
  int l1, l2, c1, c2; Node( int l1 = maxn, int l2 = -maxn, int c1 = maxn, int c2 = -maxn ) : l1(l1), l2(l2), c1(c1), c2(c2) {}
  Node operator + ( Node n ){ return Node( min(l1, n.l1), max(l2, n.l2), min(c1, n.c1), max(c2, n.c2) ); }
  int area(){ return (l2 - l1 + 1)*(c2 - c1 + 1); }
} seg[4*maxn];

void update( int pos, int ini, int fim, int id, int a, int b ){
  if( ini == fim ){ seg[pos] = Node(a, a, b, b); return; }
  int l = 2*pos, r = 2*pos + 1, mid = (ini + fim)/2;
  if( id <= mid ) update( l, ini, mid, id, a, b );
  else update( r, mid + 1, fim, id, a, b );
  seg[pos] = seg[l] + seg[r];
}

Node query( int pos, int ini, int fim, int ki, int kf ){
  if( ki > fim || ini > kf ) return seg[0];
  if( ki <= ini && fim <= kf ) return seg[pos];
  int l = 2*pos, r = 2*pos + 1, mid = (ini + fim)/2;
  return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  i = R; j = C;
  n = H, m = W;
  if( n <= 1000 && m <= 1000 ) for( int k = 0; k < n*m; k++ ) update( 1, 0, n*m - 1, k, i[k], j[k] );
  else{
    for( int k = 1; k <= H*W; k++ ){
      linha1[k] = min(linha1[k - 1], i[k - 1] );
      linha2[k] = max(linha2[k - 1], i[k - 1] );
      coluna1[k] = min(coluna1[k - 1], j[k - 1] );
      coluna2[k] = max(coluna2[k - 1], j[k - 1] );
      if( (linha2[k] - linha1[k] + 1)*(coluna2[k] - coluna1[k] + 1) == k ){ marc[k] = 1; resp++; }
    }
  }
}

int swap_seats(int a, int b) {
  swap( i[a], i[b] ); swap( j[a], j[b] );
  if( n <= 1000 && m <= 1000 ){
    update( 1, 0, n*m - 1, a, i[a], j[a] );
    update( 1, 0, n*m - 1, b, i[b], j[b] );
    int cur = 0;
    int ans = 0;
    while( cur < n*m ){
      Node aux = query( 1, 0, n*m - 1, 0, cur );
      if( aux.area() == cur + 1 ){
        ans++; cur++;
      }
      else{
        cur = aux.area() - 1;
      }
    }
    return ans;
  }
  for( int k = min(a, b) + 1; k <= max(a, b) + 1; k++ ){
    if( marc[k] ){ marc[k] = 0; resp--; }
    linha1[k] = min(linha1[k - 1], i[k - 1] );
    linha2[k] = max(linha2[k - 1], i[k - 1] );
    coluna1[k] = min(coluna1[k - 1], j[k - 1] );
    coluna2[k] = max(coluna2[k - 1], j[k - 1] );
    if( (linha2[k] - linha1[k] + 1)*(coluna2[k] - coluna1[k] + 1) == k ){ marc[k] = 1; resp++; }
  }
  return resp;
}

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