oj.uz

Submission #894763

# Submission time Handle Problem Language Result Execution time Memory
894763 2023-12-28T23:01:08 Z Shayan86 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 819 ms 167944 KB 
#include "rainbow.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
 
#define lid (id<<1)
#define rid (lid|1)
#define mid ((l+r)>>1)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll N = 2e5 + 50;
const ll Mod = 1e9 + 7;
 
struct segment{
    vector<int> idx[N], seg[N*4];
 
    void build(int l = 0, int r = N, int id = 1){
        if(l+1 == r){
            seg[id] = idx[l];
            sort(all(seg[id]));
            seg[id].resize(unique(all(seg[id])) - seg[id].begin());
            return;
        }
 
        build(l, mid, lid);
        build(mid, r, rid);
 
        seg[id].resize(seg[lid].size() + seg[rid].size());
        merge(all(seg[lid]), all(seg[rid]), seg[id].begin());
    }
 
    int get(int ql, int qr, int dwn, int up, int l = 0, int r = N, int id = 1){
        if(ql <= l && r <= qr){
            int x1 = lower_bound(all(seg[id]), up) - seg[id].begin();
            int x2 = lower_bound(all(seg[id]), dwn) - seg[id].begin();
            return x2 - x1;
        }
        if(qr <= l || r <= ql) return 0;
        return get(ql, qr, dwn, up, l, mid, lid) + get(ql, qr, dwn, up, mid, r, rid);
    }
} pnt, vert, horiz, riv;
 
ll R, C, sr, sc, M;
string s;

void add(int x, int y){
    riv.idx[x].pb(y);
    vert.idx[x-1].pb(y);
    vert.idx[x].pb(y);
    horiz.idx[x].pb(y-1);
    horiz.idx[x].pb(y);
    pnt.idx[x-1].pb(y-1);
    pnt.idx[x-1].pb(y);
    pnt.idx[x].pb(y-1);
    pnt.idx[x].pb(y);
}
 
void init(int _R, int _C, int _sr, int _sc, int _M, char *S){
    R = _R; C = _C; sr = _sr; sc = _sc; M = _M; s = S;

    int x = sc, y = sr; add(x, y);
    for(int i = 0; i < M; i++){
        if(s[i] == 'N') y--;
        else if(s[i] == 'S') y++;
        else if(s[i] == 'E') x++;
        else x--;
        add(x, y);
    }

    pnt.build(); vert.build(); horiz.build(); riv.build();
}

int colour(int ar, int ac, int br, int bc){
    ll m = vert.get(ac, bc, br + 1, ar) + horiz.get(ac, bc + 1, br, ar) + 2 * (br - ar + 1 + bc - ac + 1);
    ll n = pnt.get(ac, bc, br, ar) + 2 * (br - ar + 1 + bc - ac + 1);
    ll r = riv.get(ac, bc + 1, br + 1, ar);
    ll res = m - n + 1 - r;
    return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94296 KB Output is correct
2 Correct 33 ms 94800 KB Output is correct
3 Incorrect 31 ms 94296 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 30 ms 94296 KB Output is correct
2 Correct 33 ms 94296 KB Output is correct
3 Correct 526 ms 138532 KB Output is correct
4 Correct 756 ms 167944 KB Output is correct
5 Correct 731 ms 165268 KB Output is correct
6 Correct 518 ms 144464 KB Output is correct
7 Correct 617 ms 143440 KB Output is correct
8 Correct 274 ms 102772 KB Output is correct
9 Correct 770 ms 167536 KB Output is correct
10 Correct 819 ms 165200 KB Output is correct
11 Correct 538 ms 144464 KB Output is correct
12 Correct 291 ms 162676 KB Output is correct
13 Correct 368 ms 167336 KB Output is correct
14 Correct 397 ms 164712 KB Output is correct
15 Correct 344 ms 144468 KB Output is correct
16 Correct 531 ms 146624 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 94300 KB Output is correct
2 Correct 139 ms 167264 KB Output is correct
3 Correct 63 ms 142384 KB Output is correct
4 Correct 124 ms 152660 KB Output is correct
5 Correct 77 ms 137352 KB Output is correct
6 Correct 62 ms 110676 KB Output is correct
7 Incorrect 72 ms 118612 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94296 KB Output is correct
2 Correct 33 ms 94800 KB Output is correct
3 Incorrect 31 ms 94296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94296 KB Output is correct
2 Correct 33 ms 94800 KB Output is correct
3 Incorrect 31 ms 94296 KB Output isn't correct
4 Halted 0 ms 0 KB -