oj.uz

답안 #535424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535424 2022-03-10T09:18:53 Z mario05092929 자리 배치 (IOI18_seats) C++14
100 / 100
 2860 ms 197192 KB 
#include "seats.h"
#include <bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
typedef vector <int> vec;
const int INF = 1e7;
vec r,c;
int ans[1000005],n,m,rans;
vector <int> b[1000005];
pi a[1000005];
struct Tree {pi x;int cnt;}t[4000005];
pi la[4000005];
vec le;
pi pre[20000005];

Tree f(Tree l,Tree r) {
    if(l.x < r.x) return l;
    else if(l.x > r.x) return r;
    else return {l.x,l.cnt+r.cnt};
}

void build(int x,int l,int r) {
    if(l == r) {
        t[x] = {{0,0},1};
        return;
    }
    int mid = (l + r) >> 1;
    build(x*2,l,mid), build(x*2+1,mid+1,r);
    t[x] = f(t[x*2],t[x*2+1]);
}

void push(int x,int l,int r) {
    t[x].x.x += la[x].x;
    t[x].x.y += la[x].y;
    if(l != r) {
        la[x*2].x += la[x].x;
        la[x*2].y += la[x].y;
        la[x*2+1].x += la[x].x;
        la[x*2+1].y += la[x].y;
    }
    la[x] = {0,0};
}

void update(int x,int l,int r,int rl,int rr,pi val) {
    push(x,l,r);
    if(rr > INF-10) return;
    if(rl > r||l > rr) return;
    if(rl <= l&&r <= rr) {
        la[x].x += val.x;
        la[x].y += val.y;
        push(x,l,r);
        return;
    }
    int mid = (l + r) >> 1;
    update(x*2,l,mid,rl,rr,val), update(x*2+1,mid+1,r,rl,rr,val);
    t[x] = f(t[x*2],t[x*2+1]);
}

void pro(int x,int y,int val) {
    vec tmp;
    tmp.push_back(b[x-1][y-1]);
    tmp.push_back(b[x-1][y]);
    tmp.push_back(b[x][y-1]);
    tmp.push_back(b[x][y]);
    sort(tmp.begin(),tmp.end());
    //cout << x << ' ' << y << '\n';
    //cout << tmp[0] << ' ' << tmp[1]-1 << " : " << val << '\n';
    //cout << tmp[2] << ' ' << tmp[3]-1 << " : " << val << '\n';

    //tmp[0] = min(max(1,tmp[0]),n*m+1);
    //tmp[1] = min(n*m,tmp[1]);
    //tmp[2] = min(max(1,tmp[2]),n*m+1);
    //tmp[3] = min(n*m,tmp[3]);
    tmp[0] = max(1,tmp[0]);
    tmp[1] = min(n*m+1,tmp[1]);
    tmp[2] = max(1,tmp[2]);
    tmp[3] = min(n*m+1,tmp[3]);

    le.push_back(tmp[0]);
    le.push_back(tmp[1]);
    le.push_back(tmp[2]);
    le.push_back(tmp[3]);
    pre[tmp[0]].x += val;
    pre[tmp[1]].x -= val;
    pre[tmp[2]].y += val;
    pre[tmp[3]].y -= val;
    //update(1,1,n*m,max(1,tmp[0]),min(n*m,tmp[1]-1),{val,0});
    //update(1,1,n*m,max(1,tmp[2]),min(n*m,tmp[3]-1),{0,val});
}

void Flush() {
    sort(le.begin(),le.end());
    le.erase(unique(le.begin(),le.end()),le.end());
    pi su = make_pair(0,0);
    for(int i = 0;i < le.size()-1;i++) {
        su.x += pre[le[i]].x;
        su.y += pre[le[i]].y;
        update(1,1,n*m,le[i],le[i+1]-1,su);
    }
    for(int i : le) pre[i] = make_pair(0,0);
    le.clear();
}

void give_initial_chart(int H,int W,vec R,vec C) {
    r = R, c = C; n = H, m = W;
    for(int i = 0;i < n*m;i++) a[i+1] = {r[i]+1,c[i]+1};
    for(int i = 0;i <= n+1;i++)  {
        b[i].resize(m+2,INF);
    }
    for(int i = 1;i <= n*m;i++) b[a[i].x][a[i].y] = i;
    build(1,1,n*m);
    for(int i = 1;i <= n+1;i++) {
        for(int j = 1;j <= m+1;j++) {
            pro(i,j,1);
        }
    }
}

int swap_seats(int A,int B) {
    A++, B++;
    swap(a[A],a[B]);
    //debug(1,1,n*m);
    //cout << '\n';
    for(int i = 0;i <= 1;i++) {
        for(int j = 0;j <= 1;j++) {
            if(a[A].x+i >= 1&&a[A].y+j >= 1&&a[A].x+i <= n+1&&a[A].y+j <= m+1) pro(a[A].x+i,a[A].y+j,-1);
            if(a[B].x+i >= 1&&a[B].y+j >= 1&&a[B].x+i <= n+1&&a[B].y+j <= m+1) pro(a[B].x+i,a[B].y+j,-1);
        }
    }
    swap(b[a[A].x][a[A].y],b[a[B].x][a[B].y]);
    for(int i = 0;i <= 1;i++) {
        for(int j = 0;j <= 1;j++) {
            if(a[A].x+i >= 1&&a[A].y+j >= 1&&a[A].x+i <= n+1&&a[A].y+j <= m+1) pro(a[A].x+i,a[A].y+j,1);
            if(a[B].x+i >= 1&&a[B].y+j >= 1&&a[B].x+i <= n+1&&a[B].y+j <= m+1) pro(a[B].x+i,a[B].y+j,1);
        }
    }
    Flush();
    //debug(1,1,n*m);
    //cout << t[1].x.x << ' ' << t[1].x.y << ' ' << t[1].cnt << '\n';
    return (t[1].x == make_pair(4,0) ? t[1].cnt : 0);
}

Compilation message

seats.cpp: In function 'void Flush()':
seats.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0;i < le.size()-1;i++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 70868 KB Output is correct
2 Correct 58 ms 70868 KB Output is correct
3 Correct 66 ms 70904 KB Output is correct
4 Correct 54 ms 70892 KB Output is correct
5 Correct 52 ms 70936 KB Output is correct
6 Correct 61 ms 70892 KB Output is correct
7 Correct 64 ms 70884 KB Output is correct
8 Correct 62 ms 70876 KB Output is correct
9 Correct 61 ms 70908 KB Output is correct
10 Correct 65 ms 70888 KB Output is correct
11 Correct 63 ms 70912 KB Output is correct
12 Correct 49 ms 70936 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 70868 KB Output is correct
2 Correct 58 ms 70868 KB Output is correct
3 Correct 66 ms 70904 KB Output is correct
4 Correct 54 ms 70892 KB Output is correct
5 Correct 52 ms 70936 KB Output is correct
6 Correct 61 ms 70892 KB Output is correct
7 Correct 64 ms 70884 KB Output is correct
8 Correct 62 ms 70876 KB Output is correct
9 Correct 61 ms 70908 KB Output is correct
10 Correct 65 ms 70888 KB Output is correct
11 Correct 63 ms 70912 KB Output is correct
12 Correct 49 ms 70936 KB Output is correct
13 Correct 94 ms 71912 KB Output is correct
14 Correct 103 ms 71880 KB Output is correct
15 Correct 70 ms 72184 KB Output is correct
16 Correct 63 ms 72304 KB Output is correct
17 Correct 89 ms 72064 KB Output is correct
18 Correct 83 ms 71964 KB Output is correct
19 Correct 77 ms 72008 KB Output is correct
20 Correct 72 ms 72068 KB Output is correct
21 Correct 64 ms 72204 KB Output is correct
22 Correct 64 ms 72396 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1275 ms 154272 KB Output is correct
2 Correct 1095 ms 154296 KB Output is correct
3 Correct 1154 ms 154296 KB Output is correct
4 Correct 1055 ms 154296 KB Output is correct
5 Correct 1091 ms 154272 KB Output is correct
6 Correct 1159 ms 154272 KB Output is correct
7 Correct 1103 ms 154308 KB Output is correct
8 Correct 1242 ms 154272 KB Output is correct
9 Correct 1181 ms 154272 KB Output is correct
10 Correct 1234 ms 154212 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 71996 KB Output is correct
2 Correct 198 ms 78912 KB Output is correct
3 Correct 1355 ms 154296 KB Output is correct
4 Correct 1518 ms 154296 KB Output is correct
5 Correct 1498 ms 177784 KB Output is correct
6 Correct 1882 ms 197192 KB Output is correct
7 Correct 1284 ms 165356 KB Output is correct
8 Correct 1204 ms 154428 KB Output is correct
9 Correct 1294 ms 154556 KB Output is correct
10 Correct 1319 ms 165004 KB Output is correct
11 Correct 1436 ms 173816 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 72408 KB Output is correct
2 Correct 256 ms 72440 KB Output is correct
3 Correct 254 ms 72452 KB Output is correct
4 Correct 279 ms 72572 KB Output is correct
5 Correct 398 ms 73688 KB Output is correct
6 Correct 1859 ms 179372 KB Output is correct
7 Correct 1918 ms 179344 KB Output is correct
8 Correct 1912 ms 179408 KB Output is correct
9 Correct 2318 ms 179304 KB Output is correct
10 Correct 1747 ms 179304 KB Output is correct
11 Correct 1735 ms 179348 KB Output is correct
12 Correct 1664 ms 179288 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 70868 KB Output is correct
2 Correct 58 ms 70868 KB Output is correct
3 Correct 66 ms 70904 KB Output is correct
4 Correct 54 ms 70892 KB Output is correct
5 Correct 52 ms 70936 KB Output is correct
6 Correct 61 ms 70892 KB Output is correct
7 Correct 64 ms 70884 KB Output is correct
8 Correct 62 ms 70876 KB Output is correct
9 Correct 61 ms 70908 KB Output is correct
10 Correct 65 ms 70888 KB Output is correct
11 Correct 63 ms 70912 KB Output is correct
12 Correct 49 ms 70936 KB Output is correct
13 Correct 94 ms 71912 KB Output is correct
14 Correct 103 ms 71880 KB Output is correct
15 Correct 70 ms 72184 KB Output is correct
16 Correct 63 ms 72304 KB Output is correct
17 Correct 89 ms 72064 KB Output is correct
18 Correct 83 ms 71964 KB Output is correct
19 Correct 77 ms 72008 KB Output is correct
20 Correct 72 ms 72068 KB Output is correct
21 Correct 64 ms 72204 KB Output is correct
22 Correct 64 ms 72396 KB Output is correct
23 Correct 1275 ms 154272 KB Output is correct
24 Correct 1095 ms 154296 KB Output is correct
25 Correct 1154 ms 154296 KB Output is correct
26 Correct 1055 ms 154296 KB Output is correct
27 Correct 1091 ms 154272 KB Output is correct
28 Correct 1159 ms 154272 KB Output is correct
29 Correct 1103 ms 154308 KB Output is correct
30 Correct 1242 ms 154272 KB Output is correct
31 Correct 1181 ms 154272 KB Output is correct
32 Correct 1234 ms 154212 KB Output is correct
33 Correct 104 ms 71996 KB Output is correct
34 Correct 198 ms 78912 KB Output is correct
35 Correct 1355 ms 154296 KB Output is correct
36 Correct 1518 ms 154296 KB Output is correct
37 Correct 1498 ms 177784 KB Output is correct
38 Correct 1882 ms 197192 KB Output is correct
39 Correct 1284 ms 165356 KB Output is correct
40 Correct 1204 ms 154428 KB Output is correct
41 Correct 1294 ms 154556 KB Output is correct
42 Correct 1319 ms 165004 KB Output is correct
43 Correct 1436 ms 173816 KB Output is correct
44 Correct 213 ms 72408 KB Output is correct
45 Correct 256 ms 72440 KB Output is correct
46 Correct 254 ms 72452 KB Output is correct
47 Correct 279 ms 72572 KB Output is correct
48 Correct 398 ms 73688 KB Output is correct
49 Correct 1859 ms 179372 KB Output is correct
50 Correct 1918 ms 179344 KB Output is correct
51 Correct 1912 ms 179408 KB Output is correct
52 Correct 2318 ms 179304 KB Output is correct
53 Correct 1747 ms 179304 KB Output is correct
54 Correct 1735 ms 179348 KB Output is correct
55 Correct 1664 ms 179288 KB Output is correct
56 Correct 318 ms 72408 KB Output is correct
57 Correct 452 ms 72508 KB Output is correct
58 Correct 650 ms 73592 KB Output is correct
59 Correct 2129 ms 155872 KB Output is correct
60 Correct 2860 ms 155824 KB Output is correct
61 Correct 1910 ms 155888 KB Output is correct
62 Correct 1764 ms 167696 KB Output is correct
63 Correct 2808 ms 166360 KB Output is correct
64 Correct 2188 ms 164576 KB Output is correct
65 Correct 1868 ms 156100 KB Output is correct
66 Correct 2171 ms 156192 KB Output is correct
67 Correct 2159 ms 166084 KB Output is correct
68 Correct 1840 ms 168628 KB Output is correct
69 Correct 2687 ms 175448 KB Output is correct