Submission #129533

#	Time	Username	Problem	Language	Result	Execution time	Memory
129533		Talant	Seats (IOI18_seats)	C++17	5 / 100	4033 ms	60980 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

#define a first
#define b second
#define mk make_pair
#define pb push_back
#define node pair<pair<int,int>,pair<int,int> >

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);


int n,m;
int r[N],c[N];
node t[N * 4];

node combine(node c,node e) {
    c.a.a = max(c.a.a,e.a.a);
    c.a.b = min(c.a.b,e.a.b);
    c.b.a = max(c.b.a,e.b.a);
    c.b.b = min(c.b.b,e.b.b);
    return c;
}
void update (int pos,int ca,int cb,int v = 1,int tl = 1,int tr = n * m) {
      if (tl == tr) {
            t[v].a.a = ca;t[v].a.b = ca;
            t[v].b.a = cb;t[v].b.b = cb;
      }
      else {
            int tm = (tl + tr) >> 1;
            if (pos <= tm) update (pos,ca,cb,v + v,tl,tm);
            else update (pos,ca,cb,v + v + 1,tm + 1,tr);
            t[v] = combine(t[v + v],t[v + v + 1]);
      }
}
pair<pair<int,int>,pair<int,int> > get(int l,int r,int v = 1,int tl = 1,int tr = n * m) {
      if (l > tr || r < tl) return {{0,inf},{0,inf}};
      if (l <= tl && tr <= r) return t[v];
      int tm = (tl + tr) >> 1;
      return combine(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
      n = H,m = W;
      for (int i = 0; i < R.size(); i ++)
            r[i + 1] = R[i],c[i + 1] = C[i];

      for (int i = 1; i <= n * m; i ++) update(i,r[i],c[i]);
}

int swap_seats(int a, int b) {
      a ++,b ++;

      update(a,r[b],c[b]);
      update(b,r[a],c[a]);
      swap(r[a],r[b]);
      swap(c[a],c[b]);

      int i = 2,ans = 1;

      while (i <= n * m) {
            node cur = get(1,i);

            int rs = (cur.a.a - cur.a.b + 1) * (cur.b.a - cur.b.b + 1);
            if (rs == i) ans ++;
            i = max(rs,i + 1);
      }
      return ans;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:47:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < R.size(); i ++)
                       ~~^~~~~~~~~~

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