oj.uz

Submission #894757

# Submission time Handle Problem Language Result Execution time Memory
894757 2023-12-28T22:25:36 Z Shayan86 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 778 ms 170576 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){
    int m = vert.get(ac, bc, br + 1, ar) + horiz.get(ac, bc + 1, br, ar) + 2 * (br - ar + 1 + bc - ac + 1);
    int n = pnt.get(ac, bc, br, ar) + 2 * (br - ar + 1 + bc - ac + 1);
    int r = riv.get(ac, bc + 1, br + 1, ar);
    int res = m - n + 1 - r;
    return res;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94456 KB Output is correct
2 Correct 35 ms 94800 KB Output is correct
3 Incorrect 33 ms 94300 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 30 ms 94300 KB Output is correct
3 Correct 508 ms 138660 KB Output is correct
4 Correct 740 ms 170576 KB Output is correct
5 Correct 724 ms 167788 KB Output is correct
6 Correct 519 ms 147280 KB Output is correct
7 Correct 590 ms 146380 KB Output is correct
8 Correct 274 ms 105352 KB Output is correct
9 Correct 778 ms 170172 KB Output is correct
10 Correct 745 ms 167756 KB Output is correct
11 Correct 542 ms 147284 KB Output is correct
12 Correct 285 ms 165568 KB Output is correct
13 Correct 371 ms 170216 KB Output is correct
14 Correct 370 ms 168028 KB Output is correct
15 Correct 368 ms 147240 KB Output is correct
16 Correct 517 ms 149340 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 136 ms 167248 KB Output is correct
3 Correct 63 ms 142452 KB Output is correct
4 Correct 103 ms 152776 KB Output is correct
5 Correct 73 ms 137608 KB Output is correct
6 Correct 62 ms 110676 KB Output is correct
7 Incorrect 69 ms 118856 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 94456 KB Output is correct
2 Correct 35 ms 94800 KB Output is correct
3 Incorrect 33 ms 94300 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 94456 KB Output is correct
2 Correct 35 ms 94800 KB Output is correct
3 Incorrect 33 ms 94300 KB Output isn't correct
4 Halted 0 ms 0 KB -