Submission #159039

#	Time	Username	Problem	Language	Result	Execution time	Memory
159039		jhnah917	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	632 ms	4316 KiB

elephants

#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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3