oj.uz

Submission #964412

# Submission time Handle Problem Language Result Execution time Memory
964412 2024-04-16T19:33:19 Z BestCrazyNoob Seats (IOI18_seats) C++17
11 / 100
 4000 ms 39504 KB 
#include "seats.h"
#include <cassert>
#include <tuple>

using namespace std;

struct Node {
    int mn, mx;
    Node(): mn(1e9), mx(0) {}
    Node(int a): mn(a), mx(a) {}
    Node(Node l, Node r) {
        mn = min(l.mn, r.mn);
        mx = max(l.mx, r.mx);
    }
};

struct SegTree {
    int sz;
    vector<Node> tree;
    int ql, qr;
    SegTree() {}
    SegTree(vector<int> v) {
        sz = 1;
        while (sz < v.size()) sz *= 2;
        tree.resize(2*sz, Node());
        for (int i = 0; i < v.size(); i++) tree[sz+i] = Node(v[i]);
        for (int i = v.size(); i < sz; i++) tree[sz+i] = Node();
        for (int i = sz-1; i >= 1; i--) tree[i] = Node(tree[2*i], tree[2*i+1]);
    }
    void update(int i, int x) {
        i += sz;
        tree[i] = Node(x);
        while (i > 1) {
            i /= 2;
            tree[i] = Node(tree[2*i], tree[2*i+1]);
        }
    }
    Node __query(int ni, int nl, int nr) {
        if (qr <= nl || nr <= ql) return Node();
        if (ql <= nl && nr <= qr) return tree[ni];
        int nm = (nl+nr)/2;
        return Node(__query(2*ni, nl, nm), __query(2*ni+1, nm, nr));
    }
    pair<int, int> query(int l, int r) {
        ql = l;
        qr = r;
        auto res = __query(1, 0, sz);
        return {res.mn, res.mx};
    }
};

// sol1
vector<int> mxC, mnC, mxR, mnR;
int ans;

// sol2
vector<int> R, C;
SegTree rSeg, cSeg;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    assert(H <= 10'000);
    assert(W <= 10'000);
    ::R = R;
    ::C = C;
    if (C.size() > 1'000 || R.size() > 1'000) {
        // sol1
        mxC.resize(C.size());
        mnC.resize(C.size());
        mxR.resize(C.size());
        mnR.resize(C.size());
        mxC[0] = mnC[0] = C[0];
        mxR[0] = mnR[0] = R[0];
        for (int i = 1; i < C.size(); i++) {
            mxC[i] = max(C[i], mxC[i-1]);
            mxR[i] = max(R[i], mxR[i-1]);
            mnC[i] = min(C[i], mnC[i-1]);
            mnR[i] = min(R[i], mnR[i-1]);
        }
        for (int i = 0; i < C.size(); i++) {
            ans += (mxC[i] - mnC[i] + 1) * (mxR[i] - mnR[i] + 1) == i+1;
        }
    } else {
        // sol2
        rSeg = SegTree(R);
        cSeg = SegTree(C);
    }
}

int sol1(int a, int b) {
    // a < b WLOG
    if (a > b) swap(a, b);

    for (int i = a; i <= b; i++) {
        ans -= (mxC[i] - mnC[i] + 1) * (mxR[i] - mnR[i] + 1) == i+1;
    }

    swap(R[a], R[b]);
    swap(C[a], C[b]);
    if (a == 0) {
        mxC[0] = mnC[0] = C[0];
        mxR[0] = mnR[0] = R[0];
    }
    for (int i = max(1, a); i <= b; i++) {
        mxC[i] = max(C[i], mxC[i-1]);
        mxR[i] = max(R[i], mxR[i-1]);
        mnC[i] = min(C[i], mnC[i-1]);
        mnR[i] = min(R[i], mnR[i-1]);
    }

    for (int i = a; i <= b; i++) {
        ans += (mxC[i] - mnC[i] + 1) * (mxR[i] - mnR[i] + 1) == i+1;
    }
    return ans;
}

int sol2(int a, int b) {
    // update
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    rSeg.update(a, R[a]);
    rSeg.update(b, R[b]);
    cSeg.update(a, C[a]);
    cSeg.update(b, C[b]);
    // query
    int i = 1, ans = 1;
    int mnR = R[0], mnC = C[0], mxR = R[0], mxC = C[0];
    while (i < C.size()) {
        tie(mnR, mxR) = rSeg.query(0, i);
        tie(mnC, mxC) = cSeg.query(0, i);
        if ((mxR - mnR + 1) * (mxC - mnC + 1) == i) {
            ans++;
            i += min(mxR - mnR + 1, mxC - mnC + 1);
        } else {
            i = (mxR - mnR + 1) * (mxC - mnC + 1);
        }
    }
    return ans;
}

int swap_seats(int a, int b) {
    if (C.size() > 1'000 || R.size() > 1'000) return sol1(a, b);
    return sol2(a, b);
}

Compilation message

seats.cpp: In constructor 'SegTree::SegTree(std::vector<int>)':
seats.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while (sz < v.size()) sz *= 2;
      |                ~~~^~~~~~~~~~
seats.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < v.size(); i++) tree[sz+i] = Node(v[i]);
      |                         ~~^~~~~~~~~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 1; i < C.size(); i++) {
      |                         ~~^~~~~~~~~~
seats.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < C.size(); i++) {
      |                         ~~^~~~~~~~~~
seats.cpp: In function 'int sol2(int, int)':
seats.cpp:127:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     while (i < C.size()) {
      |            ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 21 ms 496 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 7 ms 500 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 4 ms 524 KB Output is correct
12 Correct 20 ms 344 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 21 ms 496 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 7 ms 500 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 4 ms 524 KB Output is correct
12 Correct 20 ms 344 KB Output is correct
13 Correct 100 ms 816 KB Output is correct
14 Correct 101 ms 848 KB Output is correct
15 Correct 109 ms 828 KB Output is correct
16 Correct 99 ms 820 KB Output is correct
17 Correct 105 ms 828 KB Output is correct
18 Correct 104 ms 824 KB Output is correct
19 Correct 111 ms 824 KB Output is correct
20 Correct 113 ms 824 KB Output is correct
21 Correct 108 ms 840 KB Output is correct
22 Correct 103 ms 828 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 836 KB Output is correct
2 Correct 244 ms 3948 KB Output is correct
3 Correct 386 ms 39504 KB Output is correct
4 Correct 378 ms 39472 KB Output is correct
5 Runtime error 183 ms 32304 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1240 KB Output is correct
2 Correct 18 ms 1388 KB Output is correct
3 Correct 205 ms 1296 KB Output is correct
4 Correct 2406 ms 1448 KB Output is correct
5 Correct 1029 ms 1876 KB Output is correct
6 Runtime error 168 ms 32844 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 21 ms 496 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 7 ms 500 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 4 ms 524 KB Output is correct
12 Correct 20 ms 344 KB Output is correct
13 Correct 100 ms 816 KB Output is correct
14 Correct 101 ms 848 KB Output is correct
15 Correct 109 ms 828 KB Output is correct
16 Correct 99 ms 820 KB Output is correct
17 Correct 105 ms 828 KB Output is correct
18 Correct 104 ms 824 KB Output is correct
19 Correct 111 ms 824 KB Output is correct
20 Correct 113 ms 824 KB Output is correct
21 Correct 108 ms 840 KB Output is correct
22 Correct 103 ms 828 KB Output is correct
23 Execution timed out 4029 ms 39472 KB Time limit exceeded
24 Halted 0 ms 0 KB -