제출 #263196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
263196		errorgorn	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	7845 ms	20388 KiB

elephants

#include "elephants.h"
#include <cmath>
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int n,sqrt_n;
int arr[150005];
vector<iii> buckets[390]; //pair points to num used and the next uncovered one
unordered_map<int,int> elephants;
int num_buckets;
int cam;
int query_mod;
void comp(int i){
    int cam_used=0;
    int last=-1;
    vector<iii>::reverse_iterator succ=buckets[i].rbegin();
    for (vector<iii>::reverse_iterator it=buckets[i].rbegin();it!=buckets[i].rend();it++){
        while ((*succ).first>(*it).first+cam){
            cam_used=(*succ).second.first;
            last=(*succ).second.second;
            succ++;
        }
        if (cam_used){
            (*it).second.first=cam_used+1;
            (*it).second.second=last;
        }
        else{
            (*it).second.first=1;
            (*it).second.second=(*it).first+cam;
        }
    }
}
void print(){
    for (int x=0;x<num_buckets;x++){
        for (vector<iii>::iterator it=buckets[x].begin();it!=buckets[x].end();it++){
            printf("%d %d %d %d\n",x,(*it).first,(*it).second.first,(*it).second.second);
        }
    }
    printf("\n");
}
void rebalance(){
    int pos[150005];
    for (int x=0;x<n;x++){
        pos[x]=arr[x];
    }
    sort(&pos[0],&pos[n]);
    for (int x=0;x<=num_buckets;x++){
        buckets[x].clear();
    }
    int iter=0;
    int prev=-1;
    for (int x=0;x<n;x++){
        if ((int)buckets[iter].size()==sqrt_n){
            iter++;
        }
        if (pos[x]!=prev){
            buckets[iter].push_back(iii(pos[x],ii(0,0)));
            prev=pos[x];
        }
    }
    num_buckets=++iter;
    buckets[num_buckets].push_back(iii(1000000005,ii(0,0)));
    for (int x=0;x<num_buckets;x++) comp(x);
}
void init(int N, int l, int pos[]){
    n=N;
    for (int x=0;x<n;x++){
        arr[x]=pos[x];
    }
    cam=l;
    sqrt_n=sqrt(n);
    for (int x=0;x<n;x++){
        elephants[pos[x]]++;
    }
    rebalance();
}
int equals(int i, int j){ //find pos of element equal to j in bucket i
    int a=0,b=buckets[i].size()-1,c;
    while (a!=b){
        c=(a+b)>>1;
        if (buckets[i][c].first>j) b=c-1;
        else if (buckets[i][c].first<j) a=c+1;
        else return c;
    }
    return a;
}
int bigger(int i,int j){ //find pos of first element greater than j in bucket i
    if (buckets[i].empty()) return 0;
    int a=0,b=buckets[i].size()-1,c;
    if (buckets[i][b].first<j) return b+1;
    while (a!=b){
        c=(a+b)>>1;
        if (buckets[i][c].first<=j) a=c+1;
        else if (c!=0 && buckets[i][c-1].first>j) b=c-1;
        else return c;
    }
    return a;
}
int update(int i, int j){
	if (elephants[arr[i]]==1){
        for (int x=0;;x++){
            if (!buckets[x].empty() && arr[i]<=(*buckets[x].rbegin()).first){
                buckets[x].erase(buckets[x].begin()+equals(x,arr[i]));
                comp(x);
                break;
            }
        }
	}
	elephants[arr[i]]--;
	arr[i]=j;
	elephants[j]++;
	if (elephants[j]==1){
        for (int x=1;;x++){
            if (!buckets[x].empty() && j<=(*buckets[x].begin()).first){
                x--;
                buckets[x].insert(buckets[x].begin()+bigger(x,j),iii(j,ii(0,0)));
                comp(x);
                break;
            }
        }
	}
	query_mod++;
	if (query_mod==sqrt_n){
        query_mod=0;
        rebalance();
	}
	//print();
	int ans=0;
    int last=-1;
    int succ;
    for (int x=0;x<num_buckets;x++){
        if (buckets[x].empty() || (*buckets[x].rbegin()).first<=last) continue;
        succ=bigger(x,last);
        ans+=buckets[x][succ].second.first;
        last=buckets[x][succ].second.second;
    }
    return ans;
}

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