oj.uz

Submission #158884

# Submission time Handle Problem Language Result Execution time Memory
158884 2019-10-19T09:59:54 Z jhnah917 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 638 ms 4344 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[t-1] - arr[i] > l) t--;
            if(arr[size] - arr[i] <= l) 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].arr[id] = now;
    group[gid].size++;
    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].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 288 ms 1508 KB Output is correct
8 Correct 313 ms 2628 KB Output is correct
9 Correct 425 ms 4344 KB Output is correct
10 Correct 458 ms 4108 KB Output is correct
11 Correct 397 ms 4088 KB Output is correct
12 Correct 638 ms 4196 KB Output is correct
13 Correct 426 ms 3960 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 288 ms 1508 KB Output is correct
8 Correct 313 ms 2628 KB Output is correct
9 Correct 425 ms 4344 KB Output is correct
10 Correct 458 ms 4108 KB Output is correct
11 Correct 397 ms 4088 KB Output is correct
12 Correct 638 ms 4196 KB Output is correct
13 Correct 426 ms 3960 KB Output is correct
14 Incorrect 35 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 288 ms 1508 KB Output is correct
8 Correct 313 ms 2628 KB Output is correct
9 Correct 425 ms 4344 KB Output is correct
10 Correct 458 ms 4108 KB Output is correct
11 Correct 397 ms 4088 KB Output is correct
12 Correct 638 ms 4196 KB Output is correct
13 Correct 426 ms 3960 KB Output is correct
14 Incorrect 35 ms 3324 KB Output isn't correct
15 Halted 0 ms 0 KB -