oj.uz

Submission #159039

# Submission time Handle Problem Language Result Execution time Memory
159039 2019-10-20T08:52:57 Z jhnah917 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 632 ms 4316 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 == sq) 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 == sq) 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 == sq) 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 376 KB Output is correct
2 Correct 2 ms 376 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 284 ms 2428 KB Output is correct
8 Correct 310 ms 2664 KB Output is correct
9 Correct 413 ms 4316 KB Output is correct
10 Correct 414 ms 4216 KB Output is correct
11 Correct 384 ms 4044 KB Output is correct
12 Correct 632 ms 4088 KB Output is correct
13 Correct 413 ms 3836 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 284 ms 2428 KB Output is correct
8 Correct 310 ms 2664 KB Output is correct
9 Correct 413 ms 4316 KB Output is correct
10 Correct 414 ms 4216 KB Output is correct
11 Correct 384 ms 4044 KB Output is correct
12 Correct 632 ms 4088 KB Output is correct
13 Correct 413 ms 3836 KB Output is correct
14 Incorrect 36 ms 3324 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 284 ms 2428 KB Output is correct
8 Correct 310 ms 2664 KB Output is correct
9 Correct 413 ms 4316 KB Output is correct
10 Correct 414 ms 4216 KB Output is correct
11 Correct 384 ms 4044 KB Output is correct
12 Correct 632 ms 4088 KB Output is correct
13 Correct 413 ms 3836 KB Output is correct
14 Incorrect 36 ms 3324 KB Output isn't correct
15 Halted 0 ms 0 KB -