Submission #549205

#	Time	Username	Problem	Language	Result	Execution time	Memory
549205		Vladth11	Simple game (IZhO17_game)	C++14	0 / 100	159 ms	262144 KiB

game

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 1000001;
const ll VMAX = 26;
const ll INF = (1LL << 55);
const ll MOD = 90000000000000001;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

vector <int> aib[NMAX * 4 + 4];
vector <int> nrm[NMAX * 4 + 4];

void baga(int node, int val, int x) {
    int poz = lower_bound(nrm[node].begin(), nrm[node].end(), val) - nrm[node].begin();
    poz++;
    for(; poz < aib[node].size(); poz += poz&(-poz)) {
        aib[node][poz] += x;
    }
}

int query(int node, int x) {
    int val = 0;
    int poz = upper_bound(nrm[node].begin(), nrm[node].end(), x) - nrm[node].begin();
    poz++;
    poz--;
    if(poz == 0)
        return 0;
    for(; poz > 0; poz -= poz&(-poz)) {
        val += aib[node][poz];
        if(poz == 0)
            break;
    }
    return val;
}

void update(int node, int st, int dr, int a, int b, int val) {
    baga(node, b, val);
    if(st == dr) {
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b, val);
    else
        update(node * 2 + 1, mid + 1, dr, a, b, val);
}

int bigger(int node, int st, int dr, int x1, int x2, int y) {
    if(x1 <= st && dr <= x2) {
        return query(node, nrm[node].back()) - query(node, y);
    }
    int mid = (st + dr) / 2;
    int sol = 0;
    if(x1 <= mid)
        sol += bigger(node * 2, st, mid, x1, x2, y);
    if(x2 > mid)
        sol += bigger(node * 2 + 1, mid + 1, dr, x1, x2, y);
    return sol;
}


int smaller(int node, int st, int dr, int x1, int x2, int y) {
    if(x1 <= st && dr <= x2) {
        return query(node, y);
    }
    int mid = (st + dr) / 2;
    int sol = 0;
    if(x1 <= mid)
        sol += smaller(node * 2, st, mid, x1, x2, y);
    if(x2 > mid)
        sol += smaller(node * 2 + 1, mid + 1, dr, x1, x2, y);
    return sol;
}

void build(int node, int st, int dr, int a, int b) {
    nrm[node].push_back(b);
    if(st == dr) {
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        build(node * 2, st, mid, a, b);
    else
        build(node * 2 + 1, mid + 1, dr, a, b);
}

int v[NMAX];

struct ura{
    int t, a, b;
};

ura queries[NMAX];
int cv[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i;
    cin >> n >> m;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        cv[i] = v[i];
    }
    for(i = 1; i < n; i++){
        build(1, 1, NMAX, v[i], v[i + 1]);
    }
    for(i = 1; i <= m; i++){
        ura x;
        cin >> x.t;
        cin >> x.a;
        if(x.t == 1){
            cin >> x.b;
            cv[x.a] = x.b;
            if(x.a > 1)
                build(1, 1, NMAX, cv[x.a - 1], cv[x.a]);
            if(x.a < n)
                build(1, 1, NMAX, cv[x.a], cv[x.a + 1]);
        }
        queries[i] = x;
    }
    for(i = 1; i <= NMAX * 4; i++){
        aib[i].resize(nrm[i].size() + 1, 0);
    }
    for(i = 1; i < n; i++){
        update(1, 1, NMAX, v[i], v[i + 1], 1);
    }
    for(i = 1; i <= m; i++){
        ura x = queries[i];
        if(x.t == 1){
            int prv = v[x.a];
            v[x.a] = x.b;
            if(x.a > 1){
                update(1, 1, NMAX, v[x.a - 1], prv, -1);
                update(1, 1, NMAX, v[x.a - 1], v[x.a], 1);
            }
            if(x.a < n){
                update(1, 1, NMAX, prv, v[x.a + 1], -1);
                update(1, 1, NMAX, v[x.a], v[x.a + 1], 1);
            }
        }else{
            int t = x.a;
            int aa = 0;
            if(t > 1){
                aa = bigger(1, 1, NMAX, 1, t - 1, t);
            }
            cout << aa + smaller(1, 1, NMAX, t + 1, NMAX, t) << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'void baga(int, int, int)':
game.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(; poz < aib[node].size(); poz += poz&(-poz)) {
      |           ~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51