oj.uz

Submission #1007393

# Submission time Handle Problem Language Result Execution time Memory
1007393 2024-06-24T18:48:58 Z c2zi6 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 10 ms 11184 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "elephants.h"

const int BUCKETSIZE = 400;

int l;
int m = 0;
int st[2*BUCKETSIZE + 20];
struct BUCKET {
    int n = 0;
    int b[2*BUCKETSIZE + 20];
    int cnt[2*BUCKETSIZE + 20];
    int mx[2*BUCKETSIZE + 20];
    void rem(int x) {
        while (b[n-1] > x) {
            st[m++] = b[--n];
        }
        --n;
        while (m) {
            b[n++] = st[--m];
        }
    }
    void add(int x) {
        while (n && b[n-1] > x) {
            st[m++] = b[--n];
        }
        b[n++] = x;
        while (m) {
            b[n++] = st[--m];
        }
    }
    void recalc() {
        reprl(i, n-1, 0) {
            int j = upper_bound(b, b+n, b[i] + l) - b;
            if (i == n) {
                cnt[i] = 1;
                mx[i] = b[i]+l;
            } else {
                cnt[i] = cnt[j]+1;
                mx[i] = mx[j];
            }
        }
    }
    void print() {
        rep(i, n) cout << b[i] << " "; cout << endl;
        rep(i, n) cout << cnt[i] << " "; cout << endl;
        rep(i, n) cout << mx[i] << " "; cout << endl;
    }
};

int n;
int a[60000];
vector<BUCKET> buk;
void recalc() {
    buk.clear();
    buk.pb(BUCKET());
    rep(i, n) {
        if (buk.back().n >= 400) {
            buk.pb(BUCKET());
        }
        buk.back().add(a[i]);
    }
    for (BUCKET& p : buk) p.recalc();
}
void add(int x) {
    for (BUCKET& p : buk) if (p.n) {
        if (x <= p.b[p.n-1]) {
            p.add(x);
            p.recalc();
            return;
        }
    }
    buk.back().add(x);
    buk.back().recalc();
}
void rem(int x) {
    for (BUCKET& p : buk) if (p.n) {
        if (x <= p.b[p.n-1]) {
            p.rem(x);
            p.recalc();
            return;
        }
    }
}

int answer() {
    int ans = 0;
    int R = -2e9;
    for (BUCKET& p : buk) if (p.n) {
        int i = upper_bound(p.b, p.b + p.n, R) - p.b;
        if (i == p.n) continue;
        ans += p.cnt[i];
        R = p.mx[i];
    }
    return ans;
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    rep(i, n) a[i] = X[i];
    recalc();
    /*for (BUCKET& p : buk) {*/
    /*    cout << "BUCKET: " << endl;*/
    /*    p.print();*/
    /*}*/
    /*cout << "ASHXATAV" << endl;*/
}

int qr = 0;
int update(int i, int y) {
    if (qr++ % 400 == 0) recalc();
    rem(a[i]);
    a[i] = y;
    add(a[i]);
    return answer();
}

Compilation message

elephants.cpp: In member function 'void BUCKET::print()':
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:75:9: note: in expansion of macro 'rep'
   75 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:75:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |                                        ^~~~
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:76:9: note: in expansion of macro 'rep'
   76 |         rep(i, n) cout << cnt[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:76:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |         rep(i, n) cout << cnt[i] << " "; cout << endl;
      |                                          ^~~~
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:77:9: note: in expansion of macro 'rep'
   77 |         rep(i, n) cout << mx[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:77:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |         rep(i, n) cout << mx[i] << " "; cout << endl;
      |                                         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8548 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8548 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8548 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 10 ms 11184 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8548 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 10 ms 11184 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8548 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 10 ms 11184 KB Output isn't correct
8 Halted 0 ms 0 KB -