oj.uz

Submission #252281

# Submission time Handle Problem Language Result Execution time Memory
252281 2020-07-25T07:00:03 Z balbit Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1368 ms 192468 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#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 >=1 && p.s >=1)
                MO(p.s, 1, p.f);
        }
    }
    PBIT(){}
};

PBIT bitV, bitEv, bitEh, bitF;

void init(signed R, signed C, signed sr, signed sc, signed 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;


signed colour(signed R1, signed C1, signed R2, signed 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);
    assert(E>=0 && V >= 0 && F >= 0);
    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(6, 3, 6, 4));
    bug(colour(1, 2, 5, 3));
}
#endif

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 44536 KB Output is correct
2 Correct 64 ms 45712 KB Output is correct
3 Incorrect 57 ms 44668 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 49 ms 44156 KB Output is correct
2 Correct 48 ms 44152 KB Output is correct
3 Correct 968 ms 127892 KB Output is correct
4 Correct 1368 ms 171016 KB Output is correct
5 Correct 1266 ms 166080 KB Output is correct
6 Correct 968 ms 132500 KB Output is correct
7 Correct 1072 ms 139436 KB Output is correct
8 Correct 498 ms 49380 KB Output is correct
9 Correct 1332 ms 170604 KB Output is correct
10 Correct 1297 ms 165988 KB Output is correct
11 Correct 1008 ms 132636 KB Output is correct
12 Correct 423 ms 174016 KB Output is correct
13 Correct 435 ms 170732 KB Output is correct
14 Correct 425 ms 165876 KB Output is correct
15 Correct 391 ms 132660 KB Output is correct
16 Correct 1039 ms 136264 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 365 ms 192468 KB Output is correct
3 Correct 232 ms 177228 KB Output is correct
4 Correct 317 ms 188468 KB Output is correct
5 Correct 224 ms 151980 KB Output is correct
6 Correct 102 ms 69380 KB Output is correct
7 Incorrect 144 ms 96476 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 44536 KB Output is correct
2 Correct 64 ms 45712 KB Output is correct
3 Incorrect 57 ms 44668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 44536 KB Output is correct
2 Correct 64 ms 45712 KB Output is correct
3 Incorrect 57 ms 44668 KB Output isn't correct
4 Halted 0 ms 0 KB -