oj.uz

Submission #160490

# Submission time Handle Problem Language Result Execution time Memory
160490 2019-10-27T20:15:19 Z jhnah917 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4314 ms 12700 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define pb push_back
using namespace std;
//using namespace __gnu_pbds; //ordered_set : find_by_order(order), order_of_key(key)
//using namespace __gnu_cxx; //crope : append(str), substr(s, e), at(idx)
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
int arr[151515];
int inp[151515];
int n, l, g;
int upcnt; //relax all when upcnt == sq
const int sq = 400;
 
struct Bucket{
    int arr[sq << 1], size;
    int cnt[sq << 1], last[sq << 1]; //현재까지 찍어야 하는 사진 수, 마지막으로 사진 찍은 위치
    void relax(){
        int t = size;
        for(int i=size; i; i--){
            while(t > i && arr[i] + l < arr[t-1]) t--;
            if(arr[i] + l >= arr[size]) cnt[i] = 1, last[i] = arr[i] + l;
            else cnt[i] = cnt[t] + 1, last[i] = last[t];
        }
    }
}group[400];
 
void relax(){
    upcnt = 0;
    int idx = 0;
    for(int i=1; i<=g; i++){
        for(int j=1; j<=group[i].size; j++){
            arr[++idx] = group[i].arr[j];
        }
        group[i].size = 0;
    }
    g = 1;
    for(int i=1; i<=idx; i++){
        if(group[g].size == 390) g++;
        group[g].arr[++group[g].size] = arr[i];
    }
    for(int i=1; i<=g; i++) group[i].relax();
}
 
void insert(int now){
    int gid, id;
    for(gid=1; gid<g; gid++){
        if(group[gid].arr[group[gid].size] > now) break;
    }
    for(id=1; id<=group[gid].size; id++){
        if(group[gid].arr[id] > now) break;
    }
    for(int i=group[gid].size; i>=id; i--) group[gid].arr[i+1] = group[gid].arr[i];
    group[gid].size++;
    group[gid].arr[id] = now;
    group[gid].relax();
}
 
int erase(int now){
    int gid;
    for(gid=1; gid<g; gid++){
        if(group[gid].arr[1] <= now && group[gid+1].arr[1] > now) break;
    }
    for(int i=1; i<=group[gid].size; i++){
        if(group[gid].arr[i] == now){
            for (; i<group[gid].size; i++) group[gid].arr[i] = group[gid].arr[i+1];
            group[gid].size--;
            break;
        }
    }
    group[gid].relax();
    return group[gid].size;
}
 
int query(){
    int ret = group[1].cnt[1], last = group[1].last[1];
    for(int i=2; i<=g; i++){
        if (!group[i].size || group[i].arr[group[i].size] <= last) continue;
        int l = 1, r = group[i].size, now;
        while (l <= r){
            int m = l + r >> 1;
            if(group[i].arr[m] > last) now = m, r = m - 1;
            else l = m + 1;
        }
        ret += group[i].cnt[now];
        last = group[i].last[now];
    }
    return ret;
}
 
void init(int N, int L, int x[]){
    n = N;
    l = L;
    g = 1;
    for(int i=0; i<n; i++){
        inp[i] = x[i];
        if(group[g].size == 390) g++;
        group[g].arr[++group[g].size] = x[i];
    }
    for(int i=1; i<=g; i++) group[i].relax();
}
 
int update(int i, int y){
    upcnt++;
    if(upcnt == 390) relax();
    if(!erase(inp[i])) relax();
    inp[i] = y; insert(y);
    return query();
}

Compilation message

elephants.cpp: In function 'int query()':
elephants.cpp:92:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m = l + r >> 1;
                     ~~^~~
elephants.cpp:97:14: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
         last = group[i].last[now];
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 282 ms 2536 KB Output is correct
8 Correct 309 ms 2552 KB Output is correct
9 Correct 420 ms 4344 KB Output is correct
10 Correct 329 ms 4192 KB Output is correct
11 Correct 374 ms 4132 KB Output is correct
12 Correct 636 ms 4248 KB Output is correct
13 Correct 347 ms 3960 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 282 ms 2536 KB Output is correct
8 Correct 309 ms 2552 KB Output is correct
9 Correct 420 ms 4344 KB Output is correct
10 Correct 329 ms 4192 KB Output is correct
11 Correct 374 ms 4132 KB Output is correct
12 Correct 636 ms 4248 KB Output is correct
13 Correct 347 ms 3960 KB Output is correct
14 Correct 328 ms 3384 KB Output is correct
15 Correct 503 ms 3512 KB Output is correct
16 Correct 1056 ms 4984 KB Output is correct
17 Correct 1214 ms 5804 KB Output is correct
18 Correct 1171 ms 5756 KB Output is correct
19 Correct 750 ms 5980 KB Output is correct
20 Correct 1104 ms 5880 KB Output is correct
21 Correct 1198 ms 5880 KB Output is correct
22 Correct 635 ms 5412 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 282 ms 2536 KB Output is correct
8 Correct 309 ms 2552 KB Output is correct
9 Correct 420 ms 4344 KB Output is correct
10 Correct 329 ms 4192 KB Output is correct
11 Correct 374 ms 4132 KB Output is correct
12 Correct 636 ms 4248 KB Output is correct
13 Correct 347 ms 3960 KB Output is correct
14 Correct 328 ms 3384 KB Output is correct
15 Correct 503 ms 3512 KB Output is correct
16 Correct 1056 ms 4984 KB Output is correct
17 Correct 1214 ms 5804 KB Output is correct
18 Correct 1171 ms 5756 KB Output is correct
19 Correct 750 ms 5980 KB Output is correct
20 Correct 1104 ms 5880 KB Output is correct
21 Correct 1198 ms 5880 KB Output is correct
22 Correct 635 ms 5412 KB Output is correct
23 Correct 3651 ms 12700 KB Output is correct
24 Correct 3710 ms 12588 KB Output is correct
25 Correct 2914 ms 12588 KB Output is correct
26 Correct 3150 ms 12536 KB Output is correct
27 Correct 3600 ms 12412 KB Output is correct
28 Correct 1498 ms 5372 KB Output is correct
29 Correct 1421 ms 5240 KB Output is correct
30 Correct 1493 ms 5280 KB Output is correct
31 Correct 1398 ms 5340 KB Output is correct
32 Correct 2532 ms 12024 KB Output is correct
33 Correct 2017 ms 11356 KB Output is correct
34 Correct 2707 ms 12280 KB Output is correct
35 Correct 1889 ms 12584 KB Output is correct
36 Correct 1081 ms 12168 KB Output is correct
37 Correct 3363 ms 12412 KB Output is correct
38 Correct 2802 ms 11224 KB Output is correct
39 Correct 3148 ms 12256 KB Output is correct
40 Correct 2714 ms 11256 KB Output is correct
41 Correct 4090 ms 12004 KB Output is correct
42 Correct 4314 ms 12264 KB Output is correct