oj.uz

Submission #777987

# Submission time Handle Problem Language Result Execution time Memory
777987 2023-07-10T01:01:18 Z Magikarp4000 Seats (IOI18_seats) C++17
17 / 100
 4000 ms 56396 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e6+5;
PII pos[MAXN];
int tp[MAXN], le[MAXN], bt[MAXN], ri[MAXN];
int n,res;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H*W;
    FOR(i,0,n) pos[i] = {C[i],R[i]};
    tp[0] = bt[0] = R[0];
    le[0] = ri[0] = C[0];
    res = 1;
    FOR(i,1,n) {
        tp[i] = min(tp[i-1], R[i]);
        le[i] = min(le[i-1], C[i]);
        bt[i] = max(bt[i-1], R[i]);
        ri[i] = max(ri[i-1], C[i]);
        int area = (bt[i]-tp[i]+1)*(ri[i]-le[i]+1);
        if (area == i+1) res++;
    }
}

int swap_seats(int a, int b) {
    if (a > b) swap(a,b);
    swap(pos[a], pos[b]);
    FOR(i,a,b+1) {
        if (i == 0) {
            tp[i] = bt[i] = pos[i].S;
            le[i] = ri[i] = pos[i].F;
            continue;
        }
        int orig = (bt[i]-tp[i]+1)*(ri[i]-le[i]+1) == i+1;
        tp[i] = min(tp[i-1], pos[i].S);
        le[i] = min(le[i-1], pos[i].F);
        bt[i] = max(bt[i-1], pos[i].S);
        ri[i] = max(ri[i-1], pos[i].F);
        int cur = (bt[i]-tp[i]+1)*(ri[i]-le[i]+1) == i+1;
        res += cur-orig;
    }
    return res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 452 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 448 KB Output is correct
9 Correct 3 ms 452 KB Output is correct
10 Correct 2 ms 408 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 78 ms 932 KB Output is correct
14 Correct 78 ms 932 KB Output is correct
15 Correct 79 ms 960 KB Output is correct
16 Correct 77 ms 944 KB Output is correct
17 Correct 82 ms 932 KB Output is correct
18 Correct 87 ms 932 KB Output is correct
19 Correct 78 ms 944 KB Output is correct
20 Correct 78 ms 932 KB Output is correct
21 Correct 77 ms 948 KB Output is correct
22 Correct 77 ms 940 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 972 KB Output is correct
2 Correct 128 ms 5136 KB Output is correct
3 Correct 322 ms 55344 KB Output is correct
4 Correct 293 ms 55372 KB Output is correct
5 Correct 277 ms 55480 KB Output is correct
6 Correct 278 ms 55344 KB Output is correct
7 Correct 277 ms 55352 KB Output is correct
8 Correct 277 ms 55340 KB Output is correct
9 Correct 295 ms 55344 KB Output is correct
10 Correct 294 ms 55384 KB Output is correct
11 Correct 341 ms 55356 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1996 KB Output is correct
2 Correct 13 ms 2000 KB Output is correct
3 Correct 19 ms 2028 KB Output is correct
4 Correct 87 ms 2024 KB Output is correct
5 Correct 758 ms 2388 KB Output is correct
6 Execution timed out 4018 ms 56396 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 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 452 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 448 KB Output is correct
9 Correct 3 ms 452 KB Output is correct
10 Correct 2 ms 408 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 78 ms 932 KB Output is correct
14 Correct 78 ms 932 KB Output is correct
15 Correct 79 ms 960 KB Output is correct
16 Correct 77 ms 944 KB Output is correct
17 Correct 82 ms 932 KB Output is correct
18 Correct 87 ms 932 KB Output is correct
19 Correct 78 ms 944 KB Output is correct
20 Correct 78 ms 932 KB Output is correct
21 Correct 77 ms 948 KB Output is correct
22 Correct 77 ms 940 KB Output is correct
23 Execution timed out 4034 ms 55356 KB Time limit exceeded
24 Halted 0 ms 0 KB -