oj.uz

Submission #66147

# Submission time Handle Problem Language Result Execution time Memory
66147 2018-08-09T21:47:13 Z Benq Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 1022 ms 105948 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;

// #define LOCAL 

#ifdef LOCAL
#else
    #include "rainbow.h"
#endif 

template<int SZ> struct Seg {
    vi v[SZ];
    vpi tmp;
    void INS(int x, int y) {
        tmp.pb({x,y});
    }
    void ins(int x, int y) { for (;x<SZ;x+=(x&-x)) v[x].pb(y); }
    int query(int x, int y) { 
        int ret = 0;
        for (;x;x-=(x&-x)) ret += ub(all(v[x]),y)-v[x].begin();
        return ret;
    }
    void build() { 
        sort(all(tmp)); tmp.erase(unique(all(tmp)),tmp.end());
        for (auto a: tmp) ins(a.f,a.s);
        FOR(i,1,SZ) {
            sort(all(v[i]));
        }
    }
    int query(int x0, int x1, int y0, int y1) {
        return query(x1,y1)-query(x0-1,y1)-query(x1,y0-1)+query(x0-1,y0-1); 
    }
};

Seg<MX> seg[4];

pi rr, cc;

void ins(pi x) {
    seg[0].INS(x.f,x.s);
    F0R(i,2) if (x.f > i) {
        seg[1].INS(x.f-i,x.s);
        F0R(j,2) if (x.s > j) seg[3].INS(x.f-i,x.s-j);
    }
    F0R(j,2) if (x.s > j) seg[2].INS(x.f,x.s-j);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    set<pi> tmp[4];
    pi cur = {sr,sc}; ins(cur);
    F0R(i,M) {
        switch(S[i]) {
            case 'N':
                cur.f --;
                break;
            case 'W':
                cur.s --;
                break;
            case 'E':
                cur.s ++;
                break;
            case 'S':
                cur.f ++;
                break;
        }
        ins(cur);
    }
    F0R(i,4) seg[i].build();
}

int query(int x0, int x1, int y0, int y1) {
    // cout << x0 << " " << x1 << " " << y0 << " " << y1 << " " << seg[0].query(x0,x1,y0,y1) << "\n";
    return 1-seg[0].query(x0,x1,y0,y1)-seg[3].query(x0,x1-1,y0,y1-1) // square, shaded
            +seg[1].query(x0,x1-1,y0,y1)+seg[2].query(x0,x1,y0,y1-1); // vert, hori
}

int colour(int ar, int ac, int br, int bc) {
    if (ar < rr.f && rr.s < br && ac < cc.f && cc.s < bc)
        return query(rr.f-1,rr.s+1,cc.f-1,cc.s+1)+1;
    return query(ar,br,ac,bc);
}


#ifdef LOCAL

#include <stdio.h>

static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}

#endif



/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19320 KB Output is correct
2 Correct 30 ms 19856 KB Output is correct
3 Incorrect 25 ms 19856 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 22 ms 19856 KB Output is correct
2 Correct 26 ms 19856 KB Output is correct
3 Correct 591 ms 51836 KB Output is correct
4 Correct 870 ms 77472 KB Output is correct
5 Correct 883 ms 79992 KB Output is correct
6 Correct 744 ms 79992 KB Output is correct
7 Correct 735 ms 79992 KB Output is correct
8 Correct 157 ms 79992 KB Output is correct
9 Correct 710 ms 91792 KB Output is correct
10 Correct 782 ms 94372 KB Output is correct
11 Correct 740 ms 94372 KB Output is correct
12 Correct 1022 ms 99664 KB Output is correct
13 Correct 680 ms 103356 KB Output is correct
14 Correct 711 ms 105948 KB Output is correct
15 Correct 713 ms 105948 KB Output is correct
16 Correct 640 ms 105948 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 105948 KB Output is correct
2 Correct 472 ms 105948 KB Output is correct
3 Correct 220 ms 105948 KB Output is correct
4 Correct 264 ms 105948 KB Output is correct
5 Correct 250 ms 105948 KB Output is correct
6 Correct 165 ms 105948 KB Output is correct
7 Incorrect 191 ms 105948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19320 KB Output is correct
2 Correct 30 ms 19856 KB Output is correct
3 Incorrect 25 ms 19856 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19320 KB Output is correct
2 Correct 30 ms 19856 KB Output is correct
3 Incorrect 25 ms 19856 KB Output isn't correct
4 Halted 0 ms 0 KB -