Submission #112784

#	Time	Username	Problem	Language	Result	Execution time	Memory
112784		imaxblue	Seats (IOI18_seats)	C++17	5 / 100	4038 ms	110484 KiB

seats

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

int h, w, n, r[1000005], c[1000005];
int lo[8000005], hi[8000005];
int lo2[8000005], hi2[8000005];
int gl, gr, v, v2, ans2;
void add(int L, int R, int N){
  if (L > gr || R <gl) return;
  if (gl <= L && R<=gr){
    //cout << L << ' ' << R << ' ' << v << ' ' << v2 << endl;
    lo[N]=hi[N] = v;
    lo2[N]=hi2[N] =v2;
    return;
  }
  add(lseg); add(rseg);
  lo[N] = min(lo[N*2+1], lo[N*2+2]);
  hi[N] = max(hi[N*2+1], hi[N*2+2]);
  lo2[N] = min(lo2[N*2+1], lo2[N*2+2]);
  hi2[N] = max(hi2[N*2+1], hi2[N*2+2]);
}
void turn(int N, int X, int Y){
  v = X; v2 = Y; gl = gr = N;
  add(0, n-1, 0);
}
pair<pii, pii> query(int L, int R, int N){
  if (L > gr || R < gl) return mp(mp(1<<30, 0), mp((1<<30), 0));
  if (gl <= L && R <= gr){
    //cout << gl << ' ' << gr << ' ' << L << ' ' << R << ' ' << lo[N] << ' ' << hi[N] << ' ' << lo2[N] << ' ' << hi2[N] << endl;
    return mp(mp(lo[N], hi[N]), mp(lo2[N], hi2[N]));
  }
  pair<pii, pii> tmp = query(lseg), tmp2 = query(rseg);
  tmp.x.x = min(tmp.x.x, tmp2.x.x);
  tmp.x.y = max(tmp.x.y, tmp2.x.y);
  tmp.y.x = min(tmp.y.x, tmp2.y.x);
  tmp.y.y = max(tmp.y.y, tmp2.y.y);
  //cout << "*" << tmp.y.y << ' ' << tmp2.y.y << endl;
  return tmp;
}
pair<pii, pii> get(int N){
  gl = 0; gr = N;
  return query(0, n-1, 0);
}
bool good[200005];
pair<pii, pii> tmp2[200005];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
  h = H;
  w = W;
  n = h*w;
  flood(lo);
  flood(lo2);
  fox(l, n){
    r[l] = R[l];
    c[l] = C[l];
    turn(l, R[l], C[l]);
  }
  int t=1;
  pair<pii, pii> tmp = mp(mp(1<<30, 0), mp(1<<30, 0));
    while(t <= n){
      tmp.x.x = min(tmp.x.x, r[t-1]);
      tmp.x.y = max(tmp.x.y, r[t-1]);
      tmp.y.x = min(tmp.y.x, c[t-1]);
      tmp.y.y = max(tmp.y.y, c[t-1]);
      tmp2[t] = tmp;
      if((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) == t){
        //cout << t << endl;
        ans2++;
        good[t] = 1;
      }
      //cout << tmp.x.x << ' ' << tmp.x.y << ' ' << tmp.y.x << ' ' << tmp.y.y << endl;
      //cout << t << endl
      t++;
    }
}
int swap_seats(int a, int b){
  int x = r[a], y = c[a];
  turn(a, r[b], c[b]);
  turn(b, x, y);
  r[a] = r[b]; c[a] = c[b];
  r[b] = x; c[b] = y;
  int t = 1, ans = 0;
  pair<pii, pii> tmp = mp(mp(1<<30, 0), mp(1<<30, 0));
  if (h <=1000 && w <= 1000){
    while(t <= n){
      tmp = get(t-1);
      while((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) > t){
        //cout << t << endl;
        t = (tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1);
        tmp = get(t-1);
      }
      //cout << tmp.x.x << ' ' << tmp.x.y << ' ' << tmp.y.x << ' ' << tmp.y.y << endl;
      //cout << t << endl;
      ans++;
      t++;
    }
    return ans;
  }
  if (a > b) swap(a, b);
  a=0;
  if (a == 0) tmp = mp(mp(1<<30, -1), mp(1<<30, -1)); else tmp = tmp2[a-1];
  for (int l = a; l <= b; ++l){
    ans2 -= good[l];
      tmp.x.x = min(tmp.x.x, r[l-1]);
      tmp.x.y = max(tmp.x.y, r[l-1]);
      tmp.y.x = min(tmp.y.x, c[l-1]);
      tmp.y.y = max(tmp.y.y, c[l-1]);
    tmp = get(l-1);
    good[l] = ((tmp.x.y - tmp.x.x+1)*(tmp.y.y-tmp.y.x+1) == l);
    tmp2[l] = tmp;
    ans2 += good[l];
  }
    return ans2;
}
/*
int32_t main(){
  int H, W, x, q, a, b;
  vector<int> R, C;
  cin >> H >> W;
  fox(l, H*W){
    cin >> x;
    R.pb(x);
  }
  fox(l, H*W){
    cin >> x;
    C.pb(x);
  }
  give_initial_chart(H, W, R, C);
  cin >> q;
  fox(l, q){
    cin >> a >> b;
    cout << swap_seats(a, b) << endl;
  }
  return 0;
}*/
/*
2 3
0 1 1 0 0 1
0 0 1 1 2 2
100
0 5
0 5
3 4

*/

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