제출 #129349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129349		Talant	자리 배치 (IOI18_seats)	C++17	5 / 100	4099 ms	57208 KiB

seats

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

#define a first
#define b second
#define mk make_pair
#define pb push_back

using namespace std;

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


int n,m;
int r[N],c[N],ans = 0;
pair<pair<int,int>,pair<int,int> > t[N * 4],cur,er;

void build (int v = 1,int tl = 1,int tr = n * m) {
      if (tl == tr) {
            t[v].a.a = r[tl];
            t[v].a.b = r[tl];
            t[v].b.a = c[tl];
            t[v].b.b = c[tl];
      }
      else {
            int tm = (tl + tr) >> 1;
            build (v + v,tl,tm);
            build (v + v + 1,tm + 1,tr);
            t[v].a.a = max(t[v + v].a.a,t[v + v + 1].a.a);
            t[v].a.b = min(t[v + v].a.b,t[v + v + 1].a.b);
            t[v].b.a = max(t[v + v].b.a,t[v + v + 1].b.a);
            t[v].b.b = min(t[v + v].b.b,t[v + v + 1].b.b);
      }
}
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].a.a = max(t[v + v].a.a,t[v + v + 1].a.a);
            t[v].a.b = min(t[v + v].a.b,t[v + v + 1].a.b);
            t[v].b.a = max(t[v + v].b.a,t[v + v + 1].b.a);
            t[v].b.b = min(t[v + v].b.b,t[v + v + 1].b.b);
      }
}
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 er;
      if (l <= tl && tr <= r)
            return t[v];

      int tm = (tl + tr) >> 1;
      pair<pair<int,int>,pair<int,int> > c,d,e;
      d = get(l,r,v + v,tl,tm);
      e = get(l,r,v + v + 1,tm + 1,tr);

      c.a.a = max(d.a.a,e.a.a);
      c.a.b = min(d.a.b,e.a.b);
      c.b.a = max(d.b.a,e.b.a);
      c.b.b = min(d.b.b,e.b.b);
      return c;
}
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];

      build();
}

int swap_seats(int a, int b) {
      a ++,b ++;
      update(a,r[b],c[b]);
      update(b,r[a],c[a]);
      int cr = r[a],cc = c[a];
      r[a] = r[b],c[a] = c[b];
      r[b] = cr,c[b] = cc;

      er = {{-inf,inf},{-inf,inf}};
      cur = {{-inf,inf},{-inf,inf}};

      int i = 1,last = 1;
      ans = 0;
      while (i <= n * m) {
            pair<pair<int,int>,pair<int,int> > tmp = get(last,i);
            cur.a.a = max(cur.a.a,tmp.a.a);
            cur.a.b = min(cur.a.b,tmp.a.b);
            cur.b.a = max(cur.b.a,tmp.b.a);
            cur.b.b = min(cur.b.b,tmp.b.b);

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

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:71: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