oj.uz

Submission #252285

# Submission time Handle Problem Language Result Execution time Memory
252285 2020-07-25T07:04:17 Z balbit Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 1346 ms 117844 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 max(0,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 49 ms 44408 KB Output is correct
2 Correct 72 ms 45048 KB Output is correct
3 Incorrect 49 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 45 ms 44152 KB Output is correct
2 Correct 46 ms 44100 KB Output is correct
3 Correct 839 ms 86536 KB Output is correct
4 Correct 1346 ms 107012 KB Output is correct
5 Correct 1147 ms 104280 KB Output is correct
6 Correct 858 ms 87808 KB Output is correct
7 Correct 900 ms 91868 KB Output is correct
8 Correct 406 ms 47084 KB Output is correct
9 Correct 1159 ms 106692 KB Output is correct
10 Correct 1161 ms 104160 KB Output is correct
11 Correct 922 ms 87848 KB Output is correct
12 Correct 388 ms 108500 KB Output is correct
13 Correct 397 ms 106216 KB Output is correct
14 Correct 386 ms 103768 KB Output is correct
15 Correct 338 ms 87436 KB Output is correct
16 Correct 1006 ms 89808 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 44152 KB Output is correct
2 Correct 297 ms 117844 KB Output is correct
3 Correct 203 ms 111320 KB Output is correct
4 Correct 262 ms 115792 KB Output is correct
5 Correct 190 ms 97692 KB Output is correct
6 Correct 99 ms 57068 KB Output is correct
7 Incorrect 141 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 49 ms 44408 KB Output is correct
2 Correct 72 ms 45048 KB Output is correct
3 Incorrect 49 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 49 ms 44408 KB Output is correct
2 Correct 72 ms 45048 KB Output is correct
3 Incorrect 49 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -