제출 #129542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129542		Talant	자리 배치 (IOI18_seats)	C++11	5 / 100	4050 ms	60160 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];
int mnx[N],mxx[N],mny[N],mxy[N],d;

node t[N * 4];

bool check (int i) {
      int sum = (mxx[i] - mnx[i] + 1) * (mxy[i] - mny[i] + 1);
      return (i == sum);
}
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];

      if (max(n,m) <= 1000) for (int i = 1; i <= n * m; i ++) update(i,r[i],c[i]);
      else {
            for (int i = 1; i <= n; i ++) {
                  if (i == 1) {
                        mxx[i] = r[i];
                        mnx[i] = r[i];
                        mxy[i] = c[i];
                        mny[i] = c[i];
                  }
                  else {
                        mxx[i] = max(mxx[i - 1],r[i]);
                        mxy[i] = max(mxy[i - 1],c[i]);
                        mnx[i] = min(mnx[i - 1],r[i]);
                        mny[i] = min(mny[i - 1],c[i]);
                  }
                  d += check(i);
            }
      }
}

int swap_seats(int a, int b) {
      if (max(n,m) <= 1000) {
            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;
      }
      else {
            a ++,b ++;
            if (a > b) swap(a,b);

            for (int i = a; i <= b; i ++)
                  d -= check(i);

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

            for (int i = a; i <= b; i ++) {
                  if (i == 1) {
                        mxx[i] = r[i];
                        mnx[i] = r[i];
                        mxy[i] = c[i];
                        mny[i] = c[i];
                  }
                  else {
                        mxx[i] = max(mxx[i - 1],r[i]);
                        mxy[i] = max(mxy[i - 1],c[i]);
                        mnx[i] = min(mnx[i - 1],r[i]);
                        mny[i] = min(mny[i - 1],c[i]);
                  }
                  d += check(i);
            }
            return d;
      }
}

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

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