oj.uz

Submission #252246

# Submission time Handle Problem Language Result Execution time Memory
252246 2020-07-25T03:27:49 Z balbit Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1317 ms 121944 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));
    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, 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 50 ms 44408 KB Output is correct
2 Correct 62 ms 45048 KB Output is correct
3 Incorrect 53 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 44152 KB Output is correct
2 Correct 48 ms 44152 KB Output is correct
3 Correct 885 ms 91492 KB Output is correct
4 Correct 1258 ms 121944 KB Output is correct
5 Correct 1228 ms 119136 KB Output is correct
6 Correct 960 ms 97500 KB Output is correct
7 Correct 1054 ms 98512 KB Output is correct
8 Correct 401 ms 46184 KB Output is correct
9 Correct 1317 ms 121808 KB Output is correct
10 Correct 1213 ms 118992 KB Output is correct
11 Correct 946 ms 97616 KB Output is correct
12 Correct 402 ms 116596 KB Output is correct
13 Correct 439 ms 121424 KB Output is correct
14 Correct 432 ms 118736 KB Output is correct
15 Correct 335 ms 97624 KB Output is correct
16 Correct 1026 ms 101464 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 44152 KB Output is correct
2 Correct 307 ms 117840 KB Output is correct
3 Correct 189 ms 111312 KB Output is correct
4 Correct 244 ms 116056 KB Output is correct
5 Correct 181 ms 97488 KB Output is correct
6 Correct 93 ms 57068 KB Output is correct
7 Incorrect 129 ms 70628 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 62 ms 45048 KB Output is correct
3 Incorrect 53 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 62 ms 45048 KB Output is correct
3 Incorrect 53 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -