oj.uz

답안 #250871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250871 2020-07-19T10:26:44 Z receed 무지개나라 (APIO17_rainbow) C++14
12 / 100
 446 ms 68328 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 << 17, 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});
    }
    for (auto &p : mh)
        sort(all(p.second));
    for (auto &p : mv)
        sort(all(p.second));
    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);
    }
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 302 ms 35256 KB Output is correct
4 Correct 433 ms 56060 KB Output is correct
5 Correct 446 ms 53752 KB Output is correct
6 Correct 322 ms 36600 KB Output is correct
7 Correct 445 ms 37112 KB Output is correct
8 Correct 120 ms 1912 KB Output is correct
9 Correct 441 ms 55544 KB Output is correct
10 Correct 439 ms 53496 KB Output is correct
11 Correct 332 ms 36856 KB Output is correct
12 Correct 295 ms 55032 KB Output is correct
13 Correct 294 ms 55800 KB Output is correct
14 Correct 313 ms 53880 KB Output is correct
15 Correct 236 ms 36600 KB Output is correct
16 Correct 352 ms 37080 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 254 ms 68220 KB Output is correct
3 Correct 232 ms 68328 KB Output is correct
4 Correct 236 ms 67980 KB Output is correct
5 Correct 170 ms 51448 KB Output is correct
6 Correct 44 ms 10360 KB Output is correct
7 Incorrect 77 ms 19192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 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 -