oj.uz

답안 #557166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557166 2022-05-04T19:54:31 Z nutella 무지개나라 (APIO17_rainbow) C++17
12 / 100
 1496 ms 154840 KB 
#include "rainbow.h"

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18

template<typename T>
void make_uniq(vector<T> &v) {
    sort(all(v));
    v.resize(unique(all(v)) - begin(v));
}

struct Fenwick {
    unordered_map<int, unordered_map<int, ll>> t;
    int n, m;
    set<pii > stt;

    Fenwick(int a, int b) {
        n = a, m = b;
    }

    Fenwick() = default;

    void init(int a, int b) {
        n = a, m = b;
    }

    void add(int x, int y) {
        if (stt.count(mp(x, y))) return;
        stt.insert(mp(x, y));
        for (int i = x; i < n; i |= (i + 1))
            for (int j = y; j < m; j |= (j + 1))
                t[i][j] += 1;
    }

    ll get(int x, int y) {
        ll ans = 0;
        for (int i = x; i > -1; i = ((i + 1) & i) - 1)
            for (int j = y; j > -1; j = ((j + 1) & j) - 1)
                ans += t[i][j];
        return ans;
    }

    ll get(int x1, int y1, int x2, int y2) {
        return get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
    }

};
const int dx[2] = {0, 1};

const int dy[2] = {1, 0};
int n, m;
vector<pair<int, int>> yy;

Fenwick fx, fy, fv, cv;
int mnx = infI, mny = infI, mxx = -infI, mxy = -infI;

auto here = [](int x, int y) -> bool {
    auto it = lower_bound(all(yy), mp(x, y));
    if (it == end(yy)) return false;
    return (*it) == mp(x, y);
};

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    --sr, --sc;
    fx.init(n, m), fy.init(n, m), fv.init(n, m), cv.init(n, m);
    yy = {{sr, sc}};
    for (int i = 0; i < M; ++i) {
        if (S[i] == 'N') --sr;
        else if (S[i] == 'S') ++sr;
        else if (S[i] == 'W') --sc;
        else ++sc;
        yy.emplace_back(sr, sc);
    }
    make_uniq(yy);

    vector<pii > pv, px, py, cvv;
    for (auto [x, y]: yy) { ;
        pv.emplace_back(x, y);
        ckmx(mxx, x);
        ckmx(mxy, y);
        ckmn(mnx, x);
        ckmn(mny, y);
        for (int i = 0; i < 2; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (here(nx, ny)) {
                if (nx == x) {
                    px.emplace_back(x, y);
                } else {
                    py.emplace_back(x, y);
                }
            }
        }
        if (here(x + 1, y) && here(x, y + 1) && here(x + 1, y + 1)) {
            cvv.emplace_back(x, y);
        }
    }

    make_uniq(pv), make_uniq(px), make_uniq(py), make_uniq(cvv);

//    for (auto [x, y]: pv)
//        fv.fake_add(x, y);
//    for (auto [x, y]: px)
//        fx.fake_add(x, y);
//    for (auto [x, y]: py)
//        fy.fake_add(x, y);
//    for (auto [x, y]: cvv)
//        cv.fake_add(x, y);
//
//    fv.build(), fx.build(), fy.build(), cv.build();

    for (auto [x, y]: pv)
        fv.add(x, y);
    for (auto [x, y]: px)
        fx.add(x, y);
    for (auto [x, y]: py)
        fy.add(x, y);
    for (auto [x, y]: cvv)
        cv.add(x, y);


}

int colour(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    --x1, --y1;
    --x2, --y2;
    ll C = 1 + (mnx > x1 && mny > y1 && mxx < x2 && mxy < y2);
    ll E = (x2 - x1 + 2) * 2 + (y2 - y1 + 2) * 2;
    E += fx.get(x1, y1, x2, y2 - 1) + fy.get(x1, y1, x2 - 1, y2);
    E += fv.get(x1, y2, x2, y2);
    E += fv.get(x1, y1, x2, y1);
    E += fv.get(x1, y1, x1, y2);
    E += fv.get(x2, y1, x2, y2);
    ll V = (x2 - x1 + 2) * 2LL + (y2 - y1 + 2) * 2LL + fv.get(x1, y1, x2, y2);
    ll cnt_squares = fx.get(x1, y1, x1, y2 - 1) + fx.get(x2, y1, x2, y2 - 1) + fy.get(x1, y1, x2 - 1, y1) +
                      fy.get(x1, y2, x2 - 1, y2);
    // .-.
    // | | <---- counted this F extra time
    // O-O
    ll cnt_on_corners = here(x1, y1) + here(x1, y2) + here(x2, y2) + here(x2, y1);
    // .-.
    // | |  <--- nums of Os, so we counted this F extra 1 time
    // .-O
    ll U = cv.get(x1, y1, x2 - 1, y2 - 1) + cnt_on_corners + cnt_squares;
    ll F = C + 1 + E - V;
    ll ans = F - U - 1;
    assert(ans >= 0);
    return (int)ans;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1254 ms 47524 KB Output is correct
4 Correct 1442 ms 61816 KB Output is correct
5 Correct 1496 ms 62732 KB Output is correct
6 Correct 1403 ms 63696 KB Output is correct
7 Correct 1054 ms 36636 KB Output is correct
8 Correct 1243 ms 42688 KB Output is correct
9 Correct 1406 ms 54100 KB Output is correct
10 Correct 1456 ms 54924 KB Output is correct
11 Correct 1388 ms 55808 KB Output is correct
12 Correct 324 ms 22784 KB Output is correct
13 Correct 309 ms 26108 KB Output is correct
14 Correct 360 ms 27556 KB Output is correct
15 Correct 333 ms 26832 KB Output is correct
16 Correct 1327 ms 59324 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 859 ms 84092 KB Output is correct
3 Correct 566 ms 102620 KB Output is correct
4 Correct 1147 ms 154840 KB Output is correct
5 Correct 610 ms 80784 KB Output is correct
6 Correct 301 ms 12080 KB Output is correct
7 Incorrect 489 ms 21548 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -