oj.uz

답안 #1007554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007554 2024-06-25T07:31:29 Z c2zi6 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
26 / 100
 9000 ms 108332 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 = 3;
const int DBUCKETSIZE = 1000;//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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 2 ms 9324 KB Output is correct
5 Correct 3 ms 9328 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 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 2 ms 9324 KB Output is correct
5 Correct 3 ms 9328 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Execution timed out 9015 ms 108332 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 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 2 ms 9324 KB Output is correct
5 Correct 3 ms 9328 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Execution timed out 9015 ms 108332 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 2 ms 9324 KB Output is correct
5 Correct 3 ms 9328 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Execution timed out 9015 ms 108332 KB Time limit exceeded
8 Halted 0 ms 0 KB -