oj.uz

답안 #252290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252290 2020-07-25T07:11:09 Z balbit 무지개나라 (APIO17_rainbow) C++14
12 / 100
 1376 ms 117716 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+2, {{-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,10,"NWESSWEWSE");
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 44408 KB Output is correct
2 Correct 69 ms 44920 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

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 44152 KB Output is correct
2 Correct 48 ms 44152 KB Output is correct
3 Correct 977 ms 84576 KB Output is correct
4 Correct 1209 ms 105652 KB Output is correct
5 Correct 1199 ms 102860 KB Output is correct
6 Correct 814 ms 86488 KB Output is correct
7 Correct 1053 ms 90568 KB Output is correct
8 Correct 426 ms 45928 KB Output is correct
9 Correct 1376 ms 105304 KB Output is correct
10 Correct 1139 ms 102992 KB Output is correct
11 Correct 899 ms 86488 KB Output is correct
12 Correct 357 ms 107740 KB Output is correct
13 Correct 405 ms 105432 KB Output is correct
14 Correct 368 ms 103000 KB Output is correct
15 Correct 339 ms 86488 KB Output is correct
16 Correct 883 ms 89044 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 44152 KB Output is correct
2 Correct 304 ms 117716 KB Output is correct
3 Correct 192 ms 111192 KB Output is correct
4 Correct 249 ms 115672 KB Output is correct
5 Correct 182 ms 97624 KB Output is correct
6 Correct 105 ms 56940 KB Output is correct
7 Incorrect 133 ms 70500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 44408 KB Output is correct
2 Correct 69 ms 44920 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

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 44408 KB Output is correct
2 Correct 69 ms 44920 KB Output is correct
3 Incorrect 53 ms 44408 KB Output isn't correct
4 Halted 0 ms 0 KB -