oj.uz

Submission #201243

# Submission time Handle Problem Language Result Execution time Memory
201243 2020-02-10T03:10:16 Z BThero Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 1922 ms 144464 KB 
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
#include "rainbow.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)2e5 + 5;
const int MAXM = (int)1e5 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dc[] = {'E', 'S', 'W', 'N'};

template<int N> struct BIT {
    vector<pii> T[N + 5];

    void update(int x, int y) {
        int stx = x;

        for (; x <= N; x |= (x + 1)) {
            T[x].pb(mp(y, stx));            
        }
    }

    void build() {
        for (int i = 1; i <= N; ++i) {
            sort(all(T[i]));
            T[i].resize(unique(all(T[i])) - T[i].begin());           
        }
    }

    ll prectS(int x, int ly, int ry) {
        ll ret = 0;
        
        for (; x > 0; --x) {
            ret += lower_bound(all(T[x]), mp(ry + 1, 0)) - lower_bound(all(T[x]), mp(ly, 0));
            x &= (x + 1);
        }

        return ret;
    }

    ll rectS(int ax, int bx, int ay, int by) {
        if (ax > bx || ay > by) {
            return 0;
        }

        return prectS(bx, ay, by) - prectS(ax - 1, ay, by);
    }
};

int mnx, mxx, mny, mxy;

BIT<200000> H[4];

pii arr[MAXM];

int n, m, k;

void init(int R, int C, int stx, int sty, int M, char *S) {
    n = R;
    m = C;
    k = M;
    arr[0] = mp(stx, sty);

    for (int i = 0; i < k; ++i) {
        int dir = find(dc, dc + 4, S[i]) - dc;
        stx += dx[dir];
        sty += dy[dir];
        arr[i + 1] = mp(stx, sty);                                
    }

    mnx = mxx = arr[0].fi;
    mny = mxy = arr[0].se;

    for (int i = 0; i <= k; ++i) {
        int x, y;
        tie(x, y) = arr[i];
        mnx = min(mnx, x);
        mxx = max(mxx, x);
        mny = min(mny, y);
        mxy = max(mxy, y);
        H[0].update(x, y);
        H[1].update(x, y);
        H[1].update(x - 1, y);
        H[2].update(x, y);
        H[2].update(x, y - 1);
        H[3].update(x, y);
        H[3].update(x - 1, y);
        H[3].update(x, y - 1);
        H[3].update(x - 1, y - 1);
    }    

    H[0].build();
    H[1].build();
    H[2].build();
    H[3].build();
}

int colour(int ax, int ay, int bx, int by) {
    ll ans = 1;

    if (ax < mnx && mxx < bx && ay < mny && mxy < by) {
        ++ans;        
    }    

    ans += H[1].rectS(ax, bx - 1, ay, by);
    ans += H[2].rectS(ax, bx, ay, by - 1);
    ans -= H[3].rectS(ax, bx - 1, ay, by - 1);
    ans -= H[0].rectS(ax, bx, ay, by);     
    return ans; 
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 19704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 19192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19064 KB Output is correct
2 Correct 463 ms 101152 KB Output is correct
3 Correct 486 ms 92220 KB Output is correct
4 Correct 456 ms 96456 KB Output is correct
5 Correct 606 ms 87900 KB Output is correct
6 Correct 801 ms 99176 KB Output is correct
7 Correct 616 ms 82764 KB Output is correct
8 Correct 1916 ms 144364 KB Output is correct
9 Correct 1836 ms 144264 KB Output is correct
10 Correct 523 ms 57060 KB Output is correct
11 Correct 863 ms 104516 KB Output is correct
12 Correct 443 ms 101116 KB Output is correct
13 Correct 472 ms 92376 KB Output is correct
14 Correct 467 ms 96580 KB Output is correct
15 Correct 593 ms 87820 KB Output is correct
16 Correct 834 ms 102992 KB Output is correct
17 Correct 915 ms 109012 KB Output is correct
18 Correct 1138 ms 121904 KB Output is correct
19 Correct 536 ms 95536 KB Output is correct
20 Correct 643 ms 107556 KB Output is correct
21 Incorrect 1922 ms 144464 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 19704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 19704 KB Output isn't correct
2 Halted 0 ms 0 KB -