oj.uz

Submission #252245

# Submission time Handle Problem Language Result Execution time Memory
252245 2020-07-25T03:23:17 Z balbit Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1287 ms 124504 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifndef BALBIT
#include "rainbow.h"
#endif

int n,m;
vector<pii> pts;
vector<pii> linev, lineh, face; // record top-left for all

bool H(pii &p) {
    return *lower_bound(ALL(pts), p) == p;
}
const int maxn = 2e5+5;

struct PBIT{
    vector<vector<pii> > s;
    void MO(int e, int v, int tm) {
        for (++e; e<maxn; e += e&-e) {
            s[e].pb({tm, s[e].back().s + v});
        }
    }
    int QU(int e, int tm) {
        int re = 0;
        for (++e; e>0; e -= e&-e) {
            re += prev(upper_bound(ALL(s[e]), pii{tm,10000000})) -> s;
        }
        return re;
    }
    int GT(int r1, int r2, int c1, int c2) {
        return QU(c2,r2) + QU(c1-1,r1-1) - QU(c2, r1-1) - QU(c1-1, r2);
    }
    PBIT (vector<pii> v){
        s.resize(maxn+1, {{-1,0}});
        // sorted by r
        for (pii p : v) {
            if (p.f >=0 && p.s >=0)
                MO(p.s, 1, p.f);
        }
    }
    PBIT(){}
};

PBIT bitV, bitEv, bitEh, bitF;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    pts.pb({sr, sc});
    for (int i = 0; i<M; ++i) {
        if (S[i] == 'N') {
            --sr;
        }
        if (S[i] == 'S') {
            ++sr;
        }
        if (S[i] == 'E') {
            ++sc;
        }
        if (S[i] == 'W') {
            --sc;
        }
        pts.pb({sr, sc});
    }
    sort(ALL(pts));
    pts.resize(unique(ALL(pts)) - pts.begin());
    for (pii p : pts) {
        linev.pb({p.f-1, p.s});
        linev.pb({p.f, p.s});
        lineh.pb({p.f, p.s-1});
        lineh.pb({p.f, p.s});
        face.pb({p.f-1, p.s-1});
        face.pb({p.f, p.s-1});
        face.pb({p.f-1, p.s});
        face.pb({p.f, p.s});
    }
    bug("HI");
    sort(ALL(linev));
    sort(ALL(lineh));
    sort(ALL(face));
    linev.resize(unique(ALL(linev)) - linev.begin());
    lineh.resize(unique(ALL(lineh)) - lineh.begin());
    face.resize(unique(ALL(face)) - face.begin());
    bug("HI");
    bitV = PBIT(pts);
    bitF = PBIT(face);
    bitEh = PBIT(lineh);
    bitEv = PBIT(linev);
}

int r1, c1, r2, c2;


int colour(int R1, int C1, int R2, int C2) {
    tie(r1,c1,r2,c2) = tie(R1,C1,R2,C2);
    int V = bitV.GT(r1,r2,c1,c2);
    int F = bitF.GT(r1,r2-1,c1,c2-1);
    int E = bitEh.GT(r1,r2,c1,c2-1) + bitEv.GT(r1,r2-1,c1,c2);
    return 1-(V-E+F);
}





#ifdef BALBIT
signed main(){
    IOS();
    init(6,4,3,3,9,"NWESSWEWS");
    bug(colour(2, 3, 2, 3));
    bug(colour(3, 2, 4, 4));
    bug(colour(5, 3, 6, 4));
    bug(colour(1, 2, 5, 3));
}
#endif

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 44408 KB Output is correct
2 Correct 62 ms 45048 KB Output is correct
3 Incorrect 50 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 44224 KB Output is correct
2 Correct 46 ms 44152 KB Output is correct
3 Correct 885 ms 94044 KB Output is correct
4 Correct 1287 ms 124368 KB Output is correct
5 Correct 1218 ms 121552 KB Output is correct
6 Correct 878 ms 100312 KB Output is correct
7 Correct 919 ms 100944 KB Output is correct
8 Correct 399 ms 48876 KB Output is correct
9 Correct 1269 ms 124504 KB Output is correct
10 Correct 1232 ms 121668 KB Output is correct
11 Correct 953 ms 99928 KB Output is correct
12 Correct 377 ms 119128 KB Output is correct
13 Correct 404 ms 124056 KB Output is correct
14 Correct 417 ms 121296 KB Output is correct
15 Correct 340 ms 100176 KB Output is correct
16 Correct 994 ms 104020 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 44152 KB Output is correct
2 Correct 311 ms 117836 KB Output is correct
3 Correct 192 ms 111320 KB Output is correct
4 Correct 234 ms 115924 KB Output is correct
5 Correct 176 ms 97492 KB Output is correct
6 Correct 91 ms 57064 KB Output is correct
7 Incorrect 132 ms 70624 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 44408 KB Output is correct
2 Correct 62 ms 45048 KB Output is correct
3 Incorrect 50 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 44408 KB Output is correct
2 Correct 62 ms 45048 KB Output is correct
3 Incorrect 50 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -