oj.uz

Submission #252247

# Submission time Handle Problem Language Result Execution time Memory
252247 2020-07-25T03:38:00 Z balbit Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1345 ms 121808 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);
    ll rd = R2-R1+1, cd = C2-C1+1;
    ll V = rd * cd -bitV.GT(r1,r2,c1,c2);
    ll F = (rd - 1) * (cd - 1) - bitF.GT(r1,r2-1,c1,c2-1);
    ll E = (rd-1) * cd + (rd) * (cd-1) - (bitEh.GT(r1,r2,c1,c2-1) + bitEv.GT(r1,r2-1,c1,c2));
    bug(V, E, F);
    return V-E+F;
}





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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 44408 KB Output is correct
2 Correct 61 ms 44956 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 50 ms 44152 KB Output is correct
2 Correct 47 ms 44152 KB Output is correct
3 Correct 857 ms 91168 KB Output is correct
4 Correct 1279 ms 121808 KB Output is correct
5 Correct 1206 ms 118996 KB Output is correct
6 Correct 870 ms 97360 KB Output is correct
7 Correct 957 ms 98068 KB Output is correct
8 Correct 423 ms 45724 KB Output is correct
9 Correct 1345 ms 121384 KB Output is correct
10 Correct 1330 ms 118872 KB Output is correct
11 Correct 954 ms 97360 KB Output is correct
12 Correct 405 ms 116312 KB Output is correct
13 Correct 416 ms 121304 KB Output is correct
14 Correct 400 ms 118480 KB Output is correct
15 Correct 355 ms 97232 KB Output is correct
16 Correct 947 ms 101072 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44152 KB Output is correct
2 Correct 296 ms 117712 KB Output is correct
3 Correct 202 ms 111184 KB Output is correct
4 Correct 248 ms 115800 KB Output is correct
5 Correct 198 ms 97496 KB Output is correct
6 Correct 99 ms 56936 KB Output is correct
7 Incorrect 131 ms 70496 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 44408 KB Output is correct
2 Correct 61 ms 44956 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 50 ms 44408 KB Output is correct
2 Correct 61 ms 44956 KB Output is correct
3 Incorrect 50 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -