oj.uz

Submission #769179

# Submission time Handle Problem Language Result Execution time Memory
769179 2023-06-29T09:28:31 Z pashka Seats (IOI18_seats) C++14
17 / 100
 4000 ms 55544 KB 
#include "seats.h"

using namespace std;

int n, m;
vector<int> x;
vector<int> y;

int res;
vector<int> minx, maxx, miny, maxy;
vector<bool> pr;

void recalc() {
    minx[0] = n - 1;
    maxx[0] = 0;
    miny[0] = m - 1;
    maxy[0] = 0;
    for (int i = 0; i < n * m; i++) {
        minx[i + 1] = min(minx[i], x[i]);
        maxx[i + 1] = max(maxx[i], x[i]);
        miny[i + 1] = min(miny[i], y[i]);
        maxy[i + 1] = max(maxy[i], y[i]);
    }
    for (int i = 1; i <= n * m; i++) {
        pr[i] = ((maxx[i] - minx[i] + 1) * (maxy[i] - miny[i] + 1) == i);
    }
    res = 0;
    for (int i = 0; i < n * m; i++) {
        res += pr[i + 1];
    }
}

void recalc_part(int l, int r) {
    for (int i = l; i < r; i++) {
        minx[i + 1] = min(minx[i], x[i]);
        maxx[i + 1] = max(maxx[i], x[i]);
        miny[i + 1] = min(miny[i], y[i]);
        maxy[i + 1] = max(maxy[i], y[i]);
    }
    for (int i = l + 1; i < r + 1; i++) {
        res -= pr[i];
        pr[i] = ((maxx[i] - minx[i] + 1) * (maxy[i] - miny[i] + 1) == i);
        res += pr[i];
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    x = R;
    y = C;
    n = H;
    m = W;
    minx.resize(n * m + 1);
    maxx.resize(n * m + 1);
    miny.resize(n * m + 1);
    maxy.resize(n * m + 1);
    pr.resize(n * m + 1);
    recalc();
}


int swap_seats(int a, int b) {
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    recalc_part(min(a, b), max(a, b) + 1);
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 113 ms 708 KB Output is correct
14 Correct 104 ms 696 KB Output is correct
15 Correct 105 ms 696 KB Output is correct
16 Correct 101 ms 696 KB Output is correct
17 Correct 104 ms 696 KB Output is correct
18 Correct 105 ms 700 KB Output is correct
19 Correct 108 ms 708 KB Output is correct
20 Correct 101 ms 692 KB Output is correct
21 Correct 102 ms 696 KB Output is correct
22 Correct 112 ms 700 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4051 ms 39468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 716 KB Output is correct
2 Correct 222 ms 3796 KB Output is correct
3 Correct 515 ms 53740 KB Output is correct
4 Correct 420 ms 47616 KB Output is correct
5 Correct 393 ms 52244 KB Output is correct
6 Correct 380 ms 55500 KB Output is correct
7 Correct 378 ms 55448 KB Output is correct
8 Correct 377 ms 55456 KB Output is correct
9 Correct 393 ms 55500 KB Output is correct
10 Correct 373 ms 55448 KB Output is correct
11 Correct 420 ms 55544 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1324 KB Output is correct
2 Correct 13 ms 1360 KB Output is correct
3 Correct 22 ms 1368 KB Output is correct
4 Correct 114 ms 1612 KB Output is correct
5 Correct 1042 ms 1816 KB Output is correct
6 Execution timed out 4051 ms 39868 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 113 ms 708 KB Output is correct
14 Correct 104 ms 696 KB Output is correct
15 Correct 105 ms 696 KB Output is correct
16 Correct 101 ms 696 KB Output is correct
17 Correct 104 ms 696 KB Output is correct
18 Correct 105 ms 700 KB Output is correct
19 Correct 108 ms 708 KB Output is correct
20 Correct 101 ms 692 KB Output is correct
21 Correct 102 ms 696 KB Output is correct
22 Correct 112 ms 700 KB Output is correct
23 Execution timed out 4051 ms 39468 KB Time limit exceeded
24 Halted 0 ms 0 KB -