oj.uz

Submission #1007557

# Submission time Handle Problem Language Result Execution time Memory
1007557 2024-06-25T07:33:04 Z c2zi6 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 1644 ms 25436 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;
const int DBUCKETSIZE = 2000;//2*BUCKETSIZE + 2;

int l;
int m = 0;
int st[DBUCKETSIZE];
struct BUCKET {
    int n = 0;
    int b[DBUCKETSIZE];
    int cnt[DBUCKETSIZE];
    int mx[DBUCKETSIZE];
    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() {
        if (n >= 2*BUCKETSIZE + 2) cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA KOD KARMIR KOD KARMIR AAAAAAAAAAAAAAAAAAAAAAAA" << endl;
        reprl(i, n-1, 0) {
            int j = upper_bound(b, b+n, b[i] + l) - b;
            if (j == 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];
int b[60000];
vector<BUCKET> buk;
void recalc() {
    rep(i, n) b[i] = a[i];
    sort(b, b+n);
    buk.clear();
    buk.pb(BUCKET());
    rep(i, n) {
        if (buk.back().n >= BUCKETSIZE) {
            buk.pb(BUCKET());
        }
        buk.back().add(b[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 print() {
    rep(i, n) cout << a[i] << " "; cout << endl;
    for (BUCKET& p : buk) {
        cout << "BUCKET: " << endl << "         ";
        p.print();
    }
    cout << "END OF PHASE ----------------------------------------------" << endl;
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    rep(i, n) a[i] = X[i];
    recalc();
}

int qr = 0;
int update(int i, int y) {
    if (qr++ % BUCKETSIZE == 0) {
        recalc();
        /*cout << "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_RECALCULATED_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" << endl;*/
    }
    rem(a[i]);
    a[i] = y;
    add(a[i]);
    /*print();*/
    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:77:9: note: in expansion of macro 'rep'
   77 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:77:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |                                        ^~~~
elephants.cpp: In function 'void 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:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, n) cout << a[i] << " "; cout << endl;
      |     ^~~
elephants.cpp:134:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  134 |     rep(i, n) cout << a[i] << " "; cout << endl;
      |                                    ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 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 8540 KB Output is correct
2 Correct 1 ms 8540 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 8640 KB Output is correct
6 Correct 1 ms 8656 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 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 8640 KB Output is correct
6 Correct 1 ms 8656 KB Output is correct
7 Correct 676 ms 11644 KB Output is correct
8 Correct 676 ms 12288 KB Output is correct
9 Correct 713 ms 14608 KB Output is correct
10 Correct 798 ms 14608 KB Output is correct
11 Correct 743 ms 14608 KB Output is correct
12 Correct 1092 ms 14868 KB Output is correct
13 Correct 744 ms 13872 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 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 8640 KB Output is correct
6 Correct 1 ms 8656 KB Output is correct
7 Correct 676 ms 11644 KB Output is correct
8 Correct 676 ms 12288 KB Output is correct
9 Correct 713 ms 14608 KB Output is correct
10 Correct 798 ms 14608 KB Output is correct
11 Correct 743 ms 14608 KB Output is correct
12 Correct 1092 ms 14868 KB Output is correct
13 Correct 744 ms 13872 KB Output is correct
14 Correct 748 ms 12288 KB Output is correct
15 Correct 864 ms 12304 KB Output is correct
16 Correct 1644 ms 13872 KB Output is correct
17 Runtime error 25 ms 25436 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 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 8640 KB Output is correct
6 Correct 1 ms 8656 KB Output is correct
7 Correct 676 ms 11644 KB Output is correct
8 Correct 676 ms 12288 KB Output is correct
9 Correct 713 ms 14608 KB Output is correct
10 Correct 798 ms 14608 KB Output is correct
11 Correct 743 ms 14608 KB Output is correct
12 Correct 1092 ms 14868 KB Output is correct
13 Correct 744 ms 13872 KB Output is correct
14 Correct 748 ms 12288 KB Output is correct
15 Correct 864 ms 12304 KB Output is correct
16 Correct 1644 ms 13872 KB Output is correct
17 Runtime error 25 ms 25436 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -