oj.uz

Submission #557061

# Submission time Handle Problem Language Result Execution time Memory
557061 2022-05-04T16:49:58 Z nutella Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1321 ms 153948 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

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 build(int a, int b) {
        n = a, m = b;
    }

    void add(int x, int y, int val) {
        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] += val;
    }

    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[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int n, m;
vector<pair<int, int>>
        river,
        yy;
Fenwick fx, fy, fv, cv;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R + 1, m = C + 1;
    --sr, --sc;
    fx.build(n, m), fy.build(n, m), fv.build(n, m), cv.build(n, m);
    river = {{sr, sc}};
    set<pii > used;
    used.insert(mp(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;
        river.emplace_back(sr, sc);
    }
    yy = river;
    sort(all(yy));
    yy.resize(unique(all(yy)) - begin(yy));

    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);
    };

    for (auto [x, y]: yy) {
        fv.add(x, y, 1);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (here(nx, ny)) {
                if (nx == x) {
                    fx.add(x, min(ny, y), 1);
                } else {
                    fy.add(min(nx, x), y, 1);
                }
            }
        }
        if (here(x + 1, y) && here(x, y + 1) && here(x + 1, y + 1)) {
            cv.add(x, y, 1);
        }
    }

}

int colour(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    --x1, --y1;
    --x2, --y2;
    int C = 1;
    ll E = (x2 - x1) * 2 + (y2 - y1) * 2 + fx.get(x1 + 1, y1, x2 - 1, y2 - 1) + fy.get(x1, y1 + 1, x2 - 1, y2 - 1);
    assert(E >= 0);
    ll V = (x2 - x1 + 1) * 2 + (y2 - y1 - 1) * 2 + fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    assert(V >= 0);
    ll U = cv.get(x1, y1, x2 - 1, y2 - 1);
    assert(U >= 0);
    ll F = C + 1 + E - V;
    assert(F >= 0);
    int ans = F - U - 1;
    assert(ans >= 0);
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 821 ms 41136 KB Output is correct
4 Correct 903 ms 55388 KB Output is correct
5 Correct 992 ms 56072 KB Output is correct
6 Correct 1030 ms 57628 KB Output is correct
7 Correct 680 ms 34388 KB Output is correct
8 Correct 704 ms 32952 KB Output is correct
9 Correct 922 ms 47920 KB Output is correct
10 Correct 934 ms 48668 KB Output is correct
11 Correct 964 ms 49504 KB Output is correct
12 Correct 264 ms 22732 KB Output is correct
13 Correct 316 ms 26080 KB Output is correct
14 Correct 320 ms 27608 KB Output is correct
15 Correct 369 ms 26808 KB Output is correct
16 Correct 786 ms 51044 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 867 ms 83140 KB Output is correct
3 Correct 684 ms 101752 KB Output is correct
4 Correct 1321 ms 153948 KB Output is correct
5 Correct 705 ms 80340 KB Output is correct
6 Correct 361 ms 12136 KB Output is correct
7 Incorrect 618 ms 20852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -