oj.uz

Submission #969359

# Submission time Handle Problem Language Result Execution time Memory
969359 2024-04-25T03:34:05 Z steveonalex Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 72352 KB 
#include <bits/stdc++.h>
#include "rainbow.h"

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct PST{
    struct Node{
        int child[2];
        int sum;
        Node(){memset(child, -1, sizeof child); sum = 0;}
    };

    int L, R;
    vector<Node> a;
    vector<int> version;

    void add_child(int &x){
        x = a.size();
        a.push_back(Node());
    }

    PST(int _l, int _r){
        L = _l, R = _r;
        a.push_back(Node());
        version.push_back(0);
        build_tree(L, R, 0);
    }

    void build_tree(int l, int r, int id){
        if (l == r) return;
        int mid = (l + r) >> 1;
        add_child(a[id].child[0]); add_child(a[id].child[1]);
        build_tree(l, mid, a[id].child[0]);
        build_tree(mid + 1, r, a[id].child[1]);
    }

    void update(int i, int v, int l, int r, int id, int prev_id){
        a[id] = a[prev_id];
        a[id].sum += v;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (i <= mid){
            add_child(a[id].child[0]);
            update(i, v, l, mid, a[id].child[0], a[prev_id].child[0]);
        }
        else{
            add_child(a[id].child[1]);
            update(i, v, mid + 1, r, a[id].child[1], a[prev_id].child[1]);
        }
    }

    void update(int i, int v){
        int prev = version.back();
        version.push_back(0);
        add_child(version.back());
        update(i, v, L, R, version.back(), prev);
    }

    int get(int u, int v, int l, int r, int id){
        if (u <= l && r <= v) return a[id].sum;
        int mid = (l + r) >> 1;
        int ans = 0;
        if (u <= mid) ans += get(u, v, l, mid, a[id].child[0]);
        if (v > mid) ans += get(u, v, mid + 1, r, a[id].child[1]);
        return ans;
    }

    int get(int l, int r, int ver){
        int id = version[ver];
        return get(l, r, L, R, id);
    }

    int get_version(){return version.size();}
};

const int INF = 1e9 + 69;
const int N = 2e5 + 69;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

#define Point pair<int, int>

vector<Point> dragon, verti_edge, hori_edge, vertices;
int xL, xR, yL, yR;
int cur_face;
PST dragon_cnt(1, N);
vector<int> dragon_row;

void init(int n, int m, int sr, int sc, int k, char *S) {
    Point coord = {sr, sc};
    dragon.push_back(coord);
    for(int i = 0; i<k; ++i){
        if (S[i] == 'N') coord.first--;
        else if (S[i] == 'S') coord.first++;
        else if (S[i] == 'W') coord.second--;
        else coord.second++;

        dragon.push_back(coord);
    }

    remove_dup(dragon);

    for(pair<int, int> i: dragon){
        for(int d = 0; d < 4; ++d){
            if (d <= 1) hori_edge.push_back({i.first - (d == 0), i.second});
            else verti_edge.push_back({i.first, i.second - (d == 2)});
        }
    }

    remove_dup(hori_edge); remove_dup(verti_edge);

    for(pair<int, int> i: hori_edge) {
        vertices.push_back({i.first, i.second-1});
        vertices.push_back({i.first, i.second});
    }
    for(pair<int, int> i: verti_edge){
        vertices.push_back({i.first-1, i.second});
        vertices.push_back({i.first, i.second});
    }

    remove_dup(vertices);

    dragon_row.push_back(0);  
    vector<vector<int>> sigma(N);
    for(pair<int, int> i: dragon) sigma[i.first].push_back(i.second);
    for(int i = 1; i<N; ++i){
        for(int j: sigma[i]) dragon_cnt.update(j, 1);
        dragon_row.push_back(dragon_cnt.get_version() - 1);
    }

    // cout << "Dragon: \n";
    // for(pair<int, int> i: dragon) cout << i.first << " " << i.second << "\n";
    // cout << "Horizontal Edge: \n";
    // for(pair<int, int> i: hori_edge) cout << i.first << " " << i.second << "\n";
    // cout << "Vertical Edge: \n";
    // for(pair<int, int> i: verti_edge) cout << i.first << " " << i.second << "\n";
    // cout << "Vertices: \n";
    // for(pair<int, int> i: vertices) cout << i.first << " " << i.second << "\n";

    cur_face = 2 + hori_edge.size() + verti_edge.size() - vertices.size() - dragon.size();
    xL = yL = INF;
    xR = yR = 0;
    for(pair<int, int> i: dragon){
        maximize(xR, i.first); maximize(yR, i.second);
        minimize(xL, i.first); minimize(yL, i.second);
    }


}

int colour(int ar, int ac, int br, int bc) {
    if (ar < xL && ac < yL && br > xR && bc > yR) return cur_face;
    int cnt = 0;
    int v_cnt = ((br - ar) + (bc - ac)) * 2, e_cnt = v_cnt;
    int block_cnt = dragon_cnt.get(ac, bc, dragon_row[br]) - dragon_cnt.get(ac, bc, dragon_row[ar - 1]);
    // cout << "Block_cnt: " << block_cnt << "\n";
    for(pair<int, int> i: vertices){
        if (ar <= i.first && i.first < br && ac <= i.second && i.second < bc)
            v_cnt++;
    }
    for(pair<int, int> i: hori_edge){
        if (ac <= i.second && i.second <= bc && ar <= i.first && i.first < br)
            e_cnt++;
    }
    for(pair<int, int> i: verti_edge){
        if (ar <= i.first && i.first <= br && ac <= i.second && i.second < bc)
            e_cnt++;
    }
    return 1 + e_cnt - v_cnt - block_cnt;
}


 
// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     freopen("input.inp", "r", stdin);

//     int n, m, k; cin >> n >> m;
//     int sr, sc; cin >> sr >> sc;
//     cin >> k;
//     string s; cin >> s;
//     init(n, m, sr, sc, k, (char*) s.c_str());

//     int q; cin >> q;
//     while(q--) {
//         int a, b, c, d; cin >> a >> b >> c >> d;
//         cout << colour(a, b, c, d) << "\n";
//     }
 
//     return 0;
// }

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:195:9: warning: unused variable 'cnt' [-Wunused-variable]
  195 |     int cnt = 0;
      |         ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 13 ms 11980 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Correct 8 ms 11720 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct
6 Correct 7 ms 12236 KB Output is correct
7 Correct 7 ms 11724 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 8 ms 11980 KB Output is correct
10 Correct 7 ms 11724 KB Output is correct
11 Correct 9 ms 12236 KB Output is correct
12 Correct 12 ms 13004 KB Output is correct
13 Correct 17 ms 13004 KB Output is correct
14 Correct 18 ms 12492 KB Output is correct
15 Correct 7 ms 13004 KB Output is correct
16 Correct 7 ms 11724 KB Output is correct
17 Correct 9 ms 12748 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11724 KB Output is correct
2 Correct 9 ms 12748 KB Output is correct
3 Execution timed out 3066 ms 41364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13004 KB Output is correct
2 Correct 116 ms 71080 KB Output is correct
3 Correct 88 ms 72352 KB Output is correct
4 Correct 114 ms 70268 KB Output is correct
5 Correct 63 ms 42420 KB Output is correct
6 Correct 35 ms 23224 KB Output is correct
7 Correct 53 ms 37424 KB Output is correct
8 Correct 80 ms 45228 KB Output is correct
9 Correct 82 ms 44468 KB Output is correct
10 Correct 32 ms 21268 KB Output is correct
11 Correct 49 ms 41068 KB Output is correct
12 Correct 89 ms 72104 KB Output is correct
13 Correct 88 ms 71588 KB Output is correct
14 Correct 119 ms 72272 KB Output is correct
15 Correct 68 ms 44212 KB Output is correct
16 Correct 30 ms 22204 KB Output is correct
17 Correct 53 ms 38068 KB Output is correct
18 Correct 107 ms 71168 KB Output is correct
19 Correct 98 ms 70816 KB Output is correct
20 Correct 91 ms 71076 KB Output is correct
21 Correct 81 ms 43484 KB Output is correct
22 Correct 73 ms 44032 KB Output is correct
23 Correct 26 ms 21180 KB Output is correct
24 Correct 53 ms 40624 KB Output is correct
25 Correct 87 ms 71176 KB Output is correct
26 Correct 88 ms 69688 KB Output is correct
27 Correct 115 ms 72096 KB Output is correct
28 Correct 66 ms 43612 KB Output is correct
29 Correct 29 ms 22672 KB Output is correct
30 Correct 58 ms 38068 KB Output is correct
31 Correct 99 ms 70376 KB Output is correct
32 Correct 97 ms 70636 KB Output is correct
33 Correct 89 ms 71944 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 13 ms 11980 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Correct 8 ms 11720 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct
6 Correct 7 ms 12236 KB Output is correct
7 Correct 7 ms 11724 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 8 ms 11980 KB Output is correct
10 Correct 7 ms 11724 KB Output is correct
11 Correct 9 ms 12236 KB Output is correct
12 Correct 12 ms 13004 KB Output is correct
13 Correct 17 ms 13004 KB Output is correct
14 Correct 18 ms 12492 KB Output is correct
15 Correct 7 ms 13004 KB Output is correct
16 Correct 7 ms 11724 KB Output is correct
17 Correct 9 ms 12748 KB Output is correct
18 Execution timed out 3063 ms 41132 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11976 KB Output is correct
2 Correct 13 ms 11980 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Correct 8 ms 11720 KB Output is correct
5 Correct 14 ms 11980 KB Output is correct
6 Correct 7 ms 12236 KB Output is correct
7 Correct 7 ms 11724 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 8 ms 11980 KB Output is correct
10 Correct 7 ms 11724 KB Output is correct
11 Correct 9 ms 12236 KB Output is correct
12 Correct 12 ms 13004 KB Output is correct
13 Correct 17 ms 13004 KB Output is correct
14 Correct 18 ms 12492 KB Output is correct
15 Correct 7 ms 13004 KB Output is correct
16 Correct 7 ms 11724 KB Output is correct
17 Correct 9 ms 12748 KB Output is correct
18 Execution timed out 3063 ms 41132 KB Time limit exceeded
19 Halted 0 ms 0 KB -