제출 #1028604

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

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

const int MAXN = 150000;
int N, L;
v<int> E;


void init(int n, int l, int X[])
{
    N = n;
    L = l;
    for(int i=0; i<N; i++) E.push_back(X[i]);
}

const int BUCK = 400;
int qNum = 0;
v<int> buckInd(MAXN);
v<v<ii>> bucks(MAXN/BUCK + 1);
v<v<ii>> bucksAns(MAXN/BUCK+1);

void rebuildBuck(int b){
    bucksAns[b].resize(bucks[b].size(), {0,0});
    for(int i=bucks[b].size()-1; i>=0; i--){
        auto it = lower_bound(bucks[b].begin()+i+1, bucks[b].end(), make_pair(bucks[b][i].fi+L+1, -1));
        if(it==bucks[b].end()) bucksAns[b][i] = {1, bucks[b][i].fi+L+1};
        else{
            ii tmp = bucksAns[b][distance(bucks[b].begin(), it)];
            bucksAns[b][i] = {1 + tmp.fi, tmp.se};
        }
    }
}

void rebuild(){
    v<ii> e;
    for(int i=0; i<N; i++) e.push_back({E[i], i});
    sort(e.begin(), e.end());
    for(int i=0; i<bucks.size(); i++) bucks[i].clear();
    int b=0;
    for(auto it:e){
        if(bucks[b].size()==BUCK) b++;
        bucks[b].push_back(it);
        buckInd[it.se] = b;
    }
    for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
}

void move(int e, int x){
    int b = buckInd[e];
    bucks[b].erase(find(bucks[b].begin(), bucks[b].end(), make_pair(E[e], e)));
    rebuildBuck(b);
    E[e] = x;
    int l=0, r=bucks.size()-1;
    while(l<r){
        int m=(l+r+1)/2;
        if(bucks[m].size()>0 && bucks[m][0].fi<=x) l=m;
        else r=m-1;
    }
    auto it = upper_bound(bucks[l].begin(), bucks[l].end(), make_pair(x, e));
    bucks[l].insert(it, {x, e});
    buckInd[e] = l;
    rebuildBuck(l);
}

int ans(){
    int cur = 0;
    int ret = 0;
    for(int b=0; b<bucks.size(); b++){
        auto it = lower_bound(bucks[b].begin(), bucks[b].end(), make_pair(cur, -1));
        if(it!=bucks[b].end()){
            int i = distance(bucks[b].begin(), it);
            ret += bucksAns[b][i].fi;
            cur = bucksAns[b][i].se;
        }
    }
    return ret;
}

void debug(int b){
    for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
    cout<<endl;
}

int update(int i, int y){
    if((qNum++)%BUCK==0) rebuild();
    move(i, y);
    return ans();
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void rebuild()':
elephants.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0; i<bucks.size(); i++) bucks[i].clear();
      |                  ~^~~~~~~~~~~~~
elephants.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
      |                  ~^~~~~~~~~~~~~
elephants.cpp: In function 'int ans()':
elephants.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int b=0; b<bucks.size(); b++){
      |                  ~^~~~~~~~~~~~~
elephants.cpp: In function 'void debug(int)':
elephants.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
      |                  ~^~~~~~~~~~~~~~~~

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