oj.uz

Submission #1007380

# Submission time Handle Problem Language Result Execution time Memory
1007380 2024-06-24T18:15:04 Z c2zi6 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9 ms 10588 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"

int l;
int m = 0;
int st[800];
struct BUCKET {
    int n = 0;
    int b[800];
    int cnt[800];
    int mx[800];
    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];
BUCKET buck;

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

int update(int i, int y) {
    buck.rem(a[i]);
    a[i] = y;
    buck.add(a[i]);
    buck.recalc();
    return buck.cnt[0];
}

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:73:9: note: in expansion of macro 'rep'
   73 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:73:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |         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:74:9: note: in expansion of macro 'rep'
   74 |         rep(i, n) cout << cnt[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:74:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |         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:75:9: note: in expansion of macro 'rep'
   75 |         rep(i, n) cout << mx[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:75:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |         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 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 8536 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 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 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 9 ms 10588 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 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 9 ms 10588 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 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Incorrect 9 ms 10588 KB Output isn't correct
8 Halted 0 ms 0 KB -