Submission #985681

#	Time	Username	Problem	Language	Result	Execution time	Memory
985681		Cookie	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	3162 ms	26900 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const int mxn = 150000, sq = 400;
int n, qq = 0, l;
int x[mxn + 1], mx[mxn + 1], cnt[mxn + 1], block[mxn + 1];
vt<pii>comp[mxn + 1];
void build(int s){
    int r = sz(comp[s]);
    for(int i = sz(comp[s]) - 1; i >= 0; i--){
        while(r > 0 && comp[s][i].fi + l < comp[s][r - 1].fi)r--;
        if(r == sz(comp[s])){
            cnt[comp[s][i].se] = 1; mx[comp[s][i].se] = comp[s][i].fi + l;
        }else{
            cnt[comp[s][i].se] = cnt[comp[s][r].se] + 1; mx[comp[s][i].se] = mx[comp[s][r].se];
        }
    }
}
void solve(){
    for(int i = 0; i < n; i++){
        block[i] = i / sq;
        comp[i / sq].pb(mpp(x[i], i));
    }
    for(int i = 0; i <= (n - 1) / sq; i++)build(i);
}
void init(int N, int L, int X[])
{
    n = N; l = L;
    for(int i = 0; i < n; i++)x[i] = X[i];
    solve();
}
int getblock(int x){
    for(int i = (n - 1) / sq; i >= 0; i--){
        if(sz(comp[i]) == 0)continue;
        if(comp[i][0].fi <= x)return(i);
    }
    return(0);
}
void rebuild(){
    vt<pii>all;
    for(int i = 0; i <= (n - 1) / sq; i++){
        for(auto j: comp[i])all.pb(j);
        comp[i].clear();
    }
    for(int i = 0; i <= n - 1; i++){
        block[all[i].se] = i / sq;
        comp[i / sq].pb(all[i]);
    }
    for(int i = 0; i <= (n - 1) / sq; i++)build(i);
}
int update(int id, int y)
{   
    int bl = block[id]; 
    for(int i = 0; i < sz(comp[bl]); i++){
        if(comp[bl][i].se == id){
            comp[bl].erase(comp[bl].begin() + i);
            break;
        }
    }
    build(bl);
    x[id] = y; 
    int br = getblock(x[id]), pos = sz(comp[br]); block[id] = br;
    for(int i = 0; i < sz(comp[br]); i++){
        if(comp[br][i].fi > y){
            pos = i;
            break;
        }
    }
    comp[br].insert(comp[br].begin() + pos, mpp(x[id], id));
    build(br);
    int position = -1, camera = 0;
    for(int i = 0; i <= (n - 1) / sq; i++){
        if(sz(comp[i]) == 0)continue;
        int id = lower_bound(ALL(comp[i]), mpp(position + 1, -1)) - comp[i].begin();
        if(id == sz(comp[i]))continue;
        else{
            camera += cnt[comp[i][id].se]; position = mx[comp[i][id].se];
        }
    }
    ++qq;
    if(qq == sq){
        rebuild(); qq = 0;
    }
    return(camera);
}
/*
#define MAX_N 1000000
#define MAX_M 1000000

static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];
void my_assert(int e) {if (!e) abort();}
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&L,&M));
  for(i=0; i<N; i++)
    my_assert(1==scanf("%d",&X[i]));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}

int main()
{
  int i, ans;

  read_input();
  init(N,L,X);
  for(i=0; i<M; i++) {
    ans = update(ii[i],yy[i]);
    cout << ans << "\n";
    
  }
  printf("Correct.\n");
  return 0;
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3