oj.uz

답안 #254972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254972 2020-07-30T23:22:31 Z eohomegrownapps 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
50 / 100
 9000 ms 14260 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,l;

map<ll,pair<ll,ll>> positions; //{position, {nextpos, bucketstart}}
//num cameras to protrude outside bucket, right coord of bucketwidth
unordered_map<ll,ll> poscnt;
vector<ll> ind2coord;
vector<ll> bucketx; //x coords of buckets + INF coord
ll INF = 1e9+1;
//denotes end of sequence
ll sizev;
ll qcount = 0;
void updateBucket(int ind){
    //cout<<"updating "<<ind<<" "<<bucketx[ind]<<'\n';
    //generate bucketstart, numcameras, nextpos from positions
    auto it = positions.lower_bound(bucketx[ind+1]);
    if (it==positions.begin()){return;}
    ll ptr = ind;
    do {
        it = prev(it);
        //cout<<it->first<<'\n';
        //process
        if (it->first<bucketx[ptr]){
            return;
        }
        ll rightedge = it->first+l; //upper_bound
        if (rightedge<bucketx[ptr+1]){
            auto ub = positions.upper_bound(rightedge);
            if (ub==positions.end()){
                (it->second).first = 1;
                (it->second).second = INF;
            } else if (ub->first>=bucketx[ptr+1]){
                (it->second).first = 1;
                (it->second).second = rightedge;
            } else {
                (it->second).first = (ub->second).first+1;
                (it->second).second = (ub->second).second;
            }
        } else {
            (it->second).first = 1;
            (it->second).second = rightedge;
        }
    } while (it!=positions.begin());
    //assert(ind==0||0==1);
}

void genBuckets(){
    //cout<<"generating\n";
    bucketx.clear();
    ll len = 0;
    bucketx.push_back(-1);
    for (auto p : positions){
        if (len==0){
            bucketx.push_back(p.first);
        }
        len++;
        if (len==sizev){
            len=0;
        }
    }
    bucketx.push_back(INF);
    
    /*for (ll i : bucketx){
        //cout<<i<<", ";
    }//cout<<"\n";*/

    for (ll i = bucketx.size()-2; i>=0; i--){
        updateBucket(i);
    }
}

void init(int N, int L, int X[]) {
    n = N;l=L;
    ind2coord = vector<ll>(X,X+n);
    for (ll i = 0; i<n; i++){
        if (poscnt.find(X[i])==poscnt.end()){
            poscnt[X[i]]++;
            positions[X[i]]={INF,INF};
        } else {
            poscnt[X[i]]++;
        }
    }
    sizev = sqrt(positions.size());
    genBuckets();
}

int update(int i, int y) {
    //cout<<"update "<<i<<" "<<y<<'\n';
    //remove thing at index i
    ll oldplace = ind2coord[i];
    ind2coord[i]=y;
    ll newplace = y;
    poscnt[oldplace]--;
    if (poscnt[oldplace]==0){
        positions.erase(oldplace);
    }
    if (poscnt[newplace]==0){
        positions[newplace]={INF,INF};
    }
    poscnt[newplace]++;
    qcount++;
    if (qcount%sizev==0){
        qcount=0;
        genBuckets();
    } else {
        //cout<<oldplace<<" "<<newplace<<'\n';
        updateBucket(upper_bound(bucketx.begin(),bucketx.end(),oldplace)-bucketx.begin()-1);
        updateBucket(upper_bound(bucketx.begin(),bucketx.end(),newplace)-bucketx.begin()-1);
    }
    ll cnt = 0;
    auto ptr = positions.begin();
    while (ptr!=positions.end()){
        cnt+=ptr->second.first;
        ptr = positions.upper_bound(ptr->second.second);
    }
    assert(cnt<INF);
    return cnt;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1201 ms 5668 KB Output is correct
8 Correct 1415 ms 6296 KB Output is correct
9 Correct 4567 ms 9308 KB Output is correct
10 Correct 3603 ms 10080 KB Output is correct
11 Correct 2505 ms 9864 KB Output is correct
12 Correct 5320 ms 10100 KB Output is correct
13 Correct 4069 ms 9944 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1201 ms 5668 KB Output is correct
8 Correct 1415 ms 6296 KB Output is correct
9 Correct 4567 ms 9308 KB Output is correct
10 Correct 3603 ms 10080 KB Output is correct
11 Correct 2505 ms 9864 KB Output is correct
12 Correct 5320 ms 10100 KB Output is correct
13 Correct 4069 ms 9944 KB Output is correct
14 Correct 1716 ms 6184 KB Output is correct
15 Correct 2723 ms 8072 KB Output is correct
16 Correct 7007 ms 12496 KB Output is correct
17 Execution timed out 9097 ms 14260 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1201 ms 5668 KB Output is correct
8 Correct 1415 ms 6296 KB Output is correct
9 Correct 4567 ms 9308 KB Output is correct
10 Correct 3603 ms 10080 KB Output is correct
11 Correct 2505 ms 9864 KB Output is correct
12 Correct 5320 ms 10100 KB Output is correct
13 Correct 4069 ms 9944 KB Output is correct
14 Correct 1716 ms 6184 KB Output is correct
15 Correct 2723 ms 8072 KB Output is correct
16 Correct 7007 ms 12496 KB Output is correct
17 Execution timed out 9097 ms 14260 KB Time limit exceeded
18 Halted 0 ms 0 KB -