oj.uz

Submission #250874

# Submission time Handle Problem Language Result Execution time Memory
250874 2020-07-19T10:35:01 Z receed Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 489 ms 70628 KB 
#include "rainbow.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1 << 18, M = N * 40;
int tr[M], lv[M], rv[M], sz = 1, rt[N];
set<pair<int, int>> ss, ts;
map<int, vector<int>> mh, mv;
int lx, rx, ly, ry;

int add(int v, int p, int x, int l=0, int r=N) {
    int cv = sz++;
    tr[cv] = tr[v] + x;
    if (r - l == 1)
        lv[cv] = rv[cv] = -1;
    else if (p < (l + r) / 2) {
        lv[cv] = add(lv[v], p, x, l, (l + r) / 2);
        rv[cv] = rv[v];
    }
    else {
        lv[cv] = lv[v];
        rv[cv] = add(rv[v], p, x, (l + r) / 2, r);
    }
    return cv;
}

int sum(int v, int cl, int cr, int l=0, int r=N) {
    if (v == -1 || cr <= l || r <= cl)
        return 0;
    if (cl <= l && r <= cr)
        return tr[v];
    return sum(lv[v], cl, cr, l, (l + r) / 2) + sum(rv[v], cl, cr, (l + r) / 2, r);
}

void init(int r, int c, int sr, int sc, int m, char *s) {
    lx = rx = r;
    ly = ry = c;
    ss.insert({sr, sc});
    rep(i, m) {
        if (s[i] == 'N') sr--;
        else if (s[i] == 'S') sr++;
        else if (s[i] == 'W') sc--;
        else sc++;
        lx = min(lx, sr);
        rx = max(rx, sr);
        ly = min(ly, sc);
        ry = max(ry, sc);
        ss.insert({sr, sc});
    }
    for (auto &p : ss) {
        ts.insert(p);
        if (p.first > 1) {
            ts.insert({p.first - 1, p.second});
            if (p.second > 1)
                ts.insert({p.first - 1, p.second - 1});
        }
        if (p.second > 1)
            ts.insert({p.first, p.second - 1});
    }
    int crt = 0, ls = 0;
    for (auto &p : ts) {
        while (ls < p.first)
            rt[ls++] = crt;
        int val = -1;
        if (ss.count(p)) {
            val += 1;
            if (!ss.count({p.first, p.second + 1}))
                mh[p.first].push_back(p.second);
            if (!ss.count({p.first + 1, p.second}))
                mv[p.second].push_back(p.first);
        }
        else {
            if (ss.count({p.first, p.second + 1}))
                val++;
            if (ss.count({p.first + 1, p.second}))
                val++;
        }
        crt = add(crt, p.second, val);
    }
    for (auto &p : mh)
        sort(all(p.second));
    for (auto &p : mv)
        sort(all(p.second));
}

int colour(int ar, int ac, int br, int bc) {
    ll ans = 1 + sum(rt[br - 1], ac, bc) - sum(rt[ar - 1], ac, bc);
    // cout << ans << '\n';
    if (mh.count(br))
        ans += lower_bound(all(mh[br]), bc) - lower_bound(all(mh[br]), ac);
    if (mv.count(bc))
        ans += lower_bound(all(mv[bc]), br) - lower_bound(all(mv[bc]), ar);
    if (ss.count({br, ac}))
        ans--;
    if (ss.count({ar, bc}))
        ans--;
    if (ss.count({br, bc}))
        ans++;
    if (ar < lx && rx < br && ac < ly && ry < bc)
        ans++;
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Incorrect 2 ms 512 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 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 351 ms 35484 KB Output is correct
4 Correct 482 ms 56952 KB Output is correct
5 Correct 489 ms 54676 KB Output is correct
6 Correct 352 ms 36988 KB Output is correct
7 Correct 479 ms 37240 KB Output is correct
8 Correct 152 ms 1144 KB Output is correct
9 Correct 469 ms 56568 KB Output is correct
10 Correct 467 ms 54392 KB Output is correct
11 Correct 418 ms 36984 KB Output is correct
12 Correct 308 ms 56056 KB Output is correct
13 Correct 323 ms 56824 KB Output is correct
14 Correct 335 ms 54648 KB Output is correct
15 Correct 263 ms 36984 KB Output is correct
16 Correct 359 ms 37348 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 254 ms 70520 KB Output is correct
3 Correct 241 ms 70628 KB Output is correct
4 Correct 235 ms 70376 KB Output is correct
5 Correct 171 ms 53112 KB Output is correct
6 Correct 40 ms 10644 KB Output is correct
7 Incorrect 72 ms 19832 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Incorrect 2 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Incorrect 2 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -