답안 #129542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129542 2019-07-12T13:19:01 Z Talant 자리 배치 (IOI18_seats) C++11
5 / 100
4000 ms 60160 KB
#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;
      }
}

Compilation message

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 ++)
                       ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 29 ms 476 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 29 ms 504 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 29 ms 476 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 29 ms 504 KB Output is correct
13 Correct 16 ms 1144 KB Output is correct
14 Correct 14 ms 1144 KB Output is correct
15 Incorrect 123 ms 844 KB Output isn't correct
16 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 649 ms 56824 KB Output is correct
2 Correct 678 ms 56824 KB Output is correct
3 Correct 3820 ms 56724 KB Output is correct
4 Correct 822 ms 60160 KB Output is correct
5 Correct 787 ms 60096 KB Output is correct
6 Execution timed out 4050 ms 60152 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1144 KB Output is correct
2 Correct 115 ms 6612 KB Output is correct
3 Correct 3371 ms 56700 KB Output is correct
4 Correct 649 ms 56696 KB Output is correct
5 Incorrect 521 ms 31712 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1396 KB Output is correct
2 Correct 33 ms 1364 KB Output is correct
3 Correct 275 ms 1400 KB Output is correct
4 Correct 3000 ms 1660 KB Output is correct
5 Incorrect 1115 ms 1816 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 508 KB Output is correct
5 Correct 29 ms 476 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 10 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 29 ms 504 KB Output is correct
13 Correct 16 ms 1144 KB Output is correct
14 Correct 14 ms 1144 KB Output is correct
15 Incorrect 123 ms 844 KB Output isn't correct
16 Halted 0 ms 0 KB -