oj.uz

Submission #707550

# Submission time Handle Problem Language Result Execution time Memory
707550 2023-03-09T09:05:30 Z Danilo21 Ruka (COI15_ruka) C++14
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

class BIT{

    int n;
    vector<int> tree;

    int query(int pos) const {
        smin(pos, n);
        int sum = 0;
        for (; pos; pos -= pos & (-pos))
            sum += tree[pos];
        return sum;
    }

    void update(int pos, int x){
        if (pos <= 0) return;
        for (; pos <= n; pos += pos & (-pos))
            tree[pos] += x;
    }

public:

    void Assign(int s){ n = s; tree.assign(n+1, 0); }

    void update(int l, int r, int x){
        l++; r++;
        if (l > r) return;
        update(l, x);
        update(r+1, -x);
    }

    int query(int l, int r) const {
        l++; r++;
        if (l > r) return 0;
        return query(r) - query(l-1);
    }
};

const ll K = 5e7;

class Solver{

    int n;
    vector<int> a;
    int cursor, offset, counter;
    BIT fen;
    stack<int> stk;

public:

    Solver(const vector<int>& A){
        n = A.size();
        a = A;
        cursor = 0;
        offset = K;
        stk.push(1);
        stk.push(a[0]+1);
        counter = (stk.top() < 0 ? 1 : 0);
        fen.Assign(2*K+1);
        for (int i = 1, last = a[0]; i < n; i++){
            int x = last, y = last + a[i];
            fen.update(min(x, y) + offset, max(x, y) + offset, 1);
        }
    }

    void Backward(){
        if (!cursor) return;
        int x = stk.top(); stk.pop();
        int y = stk.top();
        if (x*y < 0) counter--;
        fen.update(min(x, y) + offset, max(x, y) + offset, 1);
        cursor--;
    }

    void Forward(){
        if (cursor == n-1) return;
        cursor++;
        int x = stk.top(), y = x+a[cursor];
        if (x*y < 0) counter++;
        fen.update(min(x, y) + offset, max(x, y) + offset, -1);
        stk.push(y);
    }

    void Change(int dx){
        offset += a[cursor] - dx;
        a[cursor] = dx;
        int x = stk.top(); stk.pop();
        if (x*stk.top() < 0) counter--;
        if (x*a[cursor] < 0) counter++;
        stk.push(x + a[cursor]);
    }

    int Query() const { return counter + fen.query(0, offset); }
};

const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m, a[mxN];
vector<char> c;

vector<int> Proccess(const vector<int>& x, const vector<int>& dx){

    Solver solver(x);
    vector<int> ans;
    for (int i = 0; i < m; i++){
        if (c[i] == 'B') solver.Backward();
        if (c[i] == 'F') solver.Forward();
        if (c[i] == 'Q') ans.pb(solver.Query());
        if (c[i] == 'C') solver.Change(dx[i]);
    }
    return ans;
}

void Solve(){

    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    cin >> m;
    vector<int> dx(m), dy(m);
    for (int i = 0; i < m; i++){
        cin >> c[i];
        if (c[i] == 'C') cin >> dx[i] >> dy[i];
    }
    vector<int> ansX = Proccess(x, dx), ansY = Proccess(y, dy);
    for (int i = 0; i < ansX.size(); i++)
        cout << ansX[i] + ansY[i] << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Compilation message

ruka.cpp: In function 'void Solve()':
ruka.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < ansX.size(); i++)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -