oj.uz

Submission #158883

# Submission time Handle Problem Language Result Execution time Memory
158883 2019-10-19T09:44:56 Z jhnah917 Dancing Elephants (IOI11_elephants) C++14
26 / 100
 21 ms 2404 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>=1; 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[g].size; j++){
            arr[++idx] = group[i].arr[j];
        }
        group[i].size = 0;
    }
    g = 1;
    for(int i=1; i<=n; 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, flag = 0;
    for(gid=1; gid<g; gid++){
        if(group[gid].arr[1] <= now && now < group[gid+1].arr[1]) 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];
    int last = group[1].last[1];
    for(int i=1; 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] = inp[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 erase(int)':
elephants.cpp:73:14: warning: unused variable 'flag' [-Wunused-variable]
     int gid, flag = 0;
              ^~~~
elephants.cpp: In function 'int query()':
elephants.cpp:96:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m = l + r >> 1;
                     ~~^~~
elephants.cpp:104: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 504 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 504 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 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 21 ms 2404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 21 ms 2404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 21 ms 2404 KB Output isn't correct
8 Halted 0 ms 0 KB -