oj.uz

Submission #557375

# Submission time Handle Problem Language Result Execution time Memory
557375 2022-05-05T08:40:34 Z nutella Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 854288 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 {
    vector<vector<ll>> t;
    vector<vector<int>> yy;
    int n;


    Fenwick() = default;

    void init(int a) {
        n = a;
        yy.resize(n);
        for (int i = 0; i < n; ++i) yy[i].clear();
        t.resize(n);
    }

    void fake_add(int x, int y) {
        assert(x < n);
        assert(x >= 0);
        for (int i = x; i < n; i |= (i + 1))
            yy[i].pb(y);
    }

    void build() {
        for (int i = 0; i < n; ++i) {
            make_uniq(yy[i]);
            t[i].assign(sz(yy[i]) + 2, 0);
        }
    }

    void add(int x, int y) {
        assert(x < n);
        assert(x >= 0);
        for (int i = x; i < n; i |= (i + 1))
            for (int j = lower_bound(all(yy[i]), y) - begin(yy[i]); j < sz(yy[i]); j |= (j + 1))
                ++t[i][j];
    }

    ll get(int x, int y) {
        ll ans = 0;
        assert(x < n);
        for (int i = x; i > -1; i = ((i + 1) & i) - 1)
            for (int j = upper_bound(all(yy[i]), y) - begin(yy[i]) - 1; j > -1; j = ((j + 1) & j) - 1)
                ans += t[i][j];
        return ans;
    }

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

};

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

const int dy[4] = {1, 0, -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) -> int {
    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 + 1), fy.init(n + 1), fv.init(n + 1), cv.init(n + 1);
    mnx = infI, mny = infI, mxx = -infI, mxy = -infI;
    yy.clear();
    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);
    mnx = infI, mny = infI, mxx = -infI, mxy = -infI;
    vector<pii > pv, px, py, cvv;
    for (auto [x, y]: yy) {
        ckmx(mxx, x);
        ckmx(mxy, y);
        ckmn(mnx, x);
        ckmn(mny, y);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx == x) {
                if (ny >= 0) {
                    py.emplace_back(x, min(y, ny));
                    pv.emplace_back(x, max(y, ny)), pv.emplace_back(x + 1, max(y, ny));
                }
            } else {
                if (nx >= 0) {
                    px.emplace_back(min(nx, x), y);
                    pv.emplace_back(max(nx, x), y), pv.emplace_back(max(nx, x), 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){
//        cout << x << " " << y << endl;
        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 smart(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    --x1, --y1;
    ll C = 1 + (mnx > x1 && mxx < x2 - 1 && mny > y1 && mxy < y2 - 1);
    ll V = (x2 - x1) * 2 + (y2 - y1) * 2 + fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    ll E = (x2 - x1) * 2 + (y2 - y1) * 2 + fx.get(x1, y1, x2 - 2, y2 - 1) + fy.get(x1, y1, x2 - 1, y2 - 2);
    ll U = cv.get(x1, y1, x2 - 1, y2 - 1);
    ll F = E - V + C + 1;
    return int(F - U - 1);
}

int stupid(int x1, int y1, int x2, int y2) {
    --x1, --y1;
    --x2, --y2;
    assert(x1 <= x2 && y1 <= y2);
    set<pii > used;
    ll C = 0;
    function<void(int, int)> dfs = [&](int x, int y) {
        if (used.count(mp(x, y))) return;
        used.insert(mp(x, y));
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!here(nx, ny) && x1 <= nx && nx <= x2 && y1 <= ny && ny <= y2) {
                dfs(nx, ny);
            }
        }
    };
    for (int x = x1; x <= x2; ++x) {
        for (int y = y1; y <= y2; ++y) {
            if (!here(x, y) && !used.count(mp(x, y))) {
                ++C;
                dfs(x, y);
            }
        }
    }
    return int(C);
}

int colour(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    int sm = smart(x1, y1, x2, y2);
    int stu = stupid(x1, y1, x2, y2);
    if (sm != stu) return -1;
    return sm;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 320 KB Output is correct
2 Correct 141 ms 608 KB Output is correct
3 Correct 377 ms 724 KB Output is correct
4 Correct 373 ms 704 KB Output is correct
5 Correct 121 ms 636 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 297 ms 616 KB Output is correct
12 Correct 252 ms 688 KB Output is correct
13 Correct 182 ms 788 KB Output is correct
14 Correct 104 ms 724 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Execution timed out 3070 ms 48564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 3058 ms 854288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 320 KB Output is correct
2 Correct 141 ms 608 KB Output is correct
3 Correct 377 ms 724 KB Output is correct
4 Correct 373 ms 704 KB Output is correct
5 Correct 121 ms 636 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 297 ms 616 KB Output is correct
12 Correct 252 ms 688 KB Output is correct
13 Correct 182 ms 788 KB Output is correct
14 Correct 104 ms 724 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Execution timed out 3077 ms 46140 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 320 KB Output is correct
2 Correct 141 ms 608 KB Output is correct
3 Correct 377 ms 724 KB Output is correct
4 Correct 373 ms 704 KB Output is correct
5 Correct 121 ms 636 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 297 ms 616 KB Output is correct
12 Correct 252 ms 688 KB Output is correct
13 Correct 182 ms 788 KB Output is correct
14 Correct 104 ms 724 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Execution timed out 3077 ms 46140 KB Time limit exceeded
19 Halted 0 ms 0 KB -