oj.uz

Submission #311007

# Submission time Handle Problem Language Result Execution time Memory
311007 2020-10-09T04:08:19 Z fishy15 Ruka (COI15_ruka) C++14
100 / 100
 476 ms 26872 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 1000000

using namespace std;

int n, m;
array<int, 2> v[MAXN];

struct node {
    int v;
    int l, r;
    node *c[2];
    node(int l, int r) : v(0), l(l), r(r) {
        c[0] = c[1] = nullptr;
    }
    void upd(int x, int v) {
        this->v += v;
        if (l != r) {
            int m = l + (r - l) / 2;
            if (x <= m) {
                if (!c[0]) c[0] = new node(l, m);
                c[0]->upd(x, v);
            } else {
                if (!c[1]) c[1] = new node(m + 1, r);
                c[1]->upd(x, v);
            }
        }
    }
    int qry(int x) {
        if (x >= r) return v;
        if (x < l) return 0;
        int res = 0;
        if (c[0]) res += c[0]->qry(x);
        if (c[1]) res += c[1]->qry(x);
        return res;
    }
};

int cur;
int x = 1;
int y = 1;
int back_x = 1;
int back_y = 1;
const int MX = 5e7 + 10;
node *l_x = new node(-MX, MX);
node *l_y = new node(-MX, MX);
node *r_x = new node(-MX, MX);
node *r_y = new node(-MX, MX);

void upd_l(int d) {
    int nx = x + d * v[cur][0];
    int ny = y + d * v[cur][1];
    l_x->upd(min(nx, x), d);
    l_x->upd(max(nx, x), -d);
    l_y->upd(min(ny, y), d);
    l_y->upd(max(ny, y), -d);
    x = nx;
    y = ny;
}

void upd_r(int d) {
    int nx = back_x - d * v[cur][0];
    int ny = back_y - d * v[cur][1];
    r_x->upd(min(back_x, nx), d);
    r_x->upd(max(back_x, nx), -d);
    r_y->upd(min(back_y, ny), d);
    r_y->upd(max(back_y, ny), -d);
    back_x = nx;
    back_y = ny;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1];
    }

    for (int i = n - 1; i >= 0; i--) {
        int nx = back_x - v[i][0];
        int ny = back_y - v[i][1];
        r_x->upd(min(back_x, nx), 1);
        r_x->upd(max(back_x, nx), -1);
        r_y->upd(min(back_y, ny), 1);
        r_y->upd(max(back_y, ny), -1);
        back_x = nx;
        back_y = ny;
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        char c; cin >> c;
        if (c == 'B') {
            if (cur > 0) {
                cur--;
                upd_l(-1);
                upd_r(1);
            }
        } else if (c == 'F') {
            if (cur < n - 1) {
                upd_l(1);
                upd_r(-1);
                cur++;
            }
        } else if (c == 'C') {
            upd_r(-1);
            cin >> v[cur][0] >> v[cur][1];
            upd_r(1);
        } else if (c == 'Q') {
            int res = l_x->qry(0) + l_y->qry(0) + r_x->qry(back_x - x) + r_y->qry(back_y - y);
            cout << res << '\n';
        }
    }

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 2 ms 568 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 137 ms 9912 KB Output is correct
6 Correct 116 ms 9336 KB Output is correct
7 Correct 116 ms 4988 KB Output is correct
8 Correct 114 ms 5020 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 137 ms 9912 KB Output is correct
6 Correct 116 ms 9336 KB Output is correct
7 Correct 116 ms 4988 KB Output is correct
8 Correct 114 ms 5020 KB Output is correct
9 Correct 408 ms 22740 KB Output is correct
10 Correct 476 ms 26872 KB Output is correct
11 Correct 377 ms 20344 KB Output is correct
12 Correct 407 ms 19320 KB Output is correct