oj.uz

Submission #263196

# Submission time Handle Problem Language Result Execution time Memory
263196 2020-08-13T13:59:28 Z errorgorn Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7845 ms 20388 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 423 ms 3620 KB Output is correct
8 Correct 493 ms 4972 KB Output is correct
9 Correct 682 ms 5604 KB Output is correct
10 Correct 911 ms 6484 KB Output is correct
11 Correct 848 ms 6300 KB Output is correct
12 Correct 1449 ms 6296 KB Output is correct
13 Correct 877 ms 6264 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 423 ms 3620 KB Output is correct
8 Correct 493 ms 4972 KB Output is correct
9 Correct 682 ms 5604 KB Output is correct
10 Correct 911 ms 6484 KB Output is correct
11 Correct 848 ms 6300 KB Output is correct
12 Correct 1449 ms 6296 KB Output is correct
13 Correct 877 ms 6264 KB Output is correct
14 Correct 573 ms 3924 KB Output is correct
15 Correct 783 ms 5744 KB Output is correct
16 Correct 1952 ms 6828 KB Output is correct
17 Correct 2320 ms 10524 KB Output is correct
18 Correct 2482 ms 10524 KB Output is correct
19 Correct 1523 ms 10532 KB Output is correct
20 Correct 2412 ms 10596 KB Output is correct
21 Correct 2453 ms 10520 KB Output is correct
22 Correct 1441 ms 10520 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 423 ms 3620 KB Output is correct
8 Correct 493 ms 4972 KB Output is correct
9 Correct 682 ms 5604 KB Output is correct
10 Correct 911 ms 6484 KB Output is correct
11 Correct 848 ms 6300 KB Output is correct
12 Correct 1449 ms 6296 KB Output is correct
13 Correct 877 ms 6264 KB Output is correct
14 Correct 573 ms 3924 KB Output is correct
15 Correct 783 ms 5744 KB Output is correct
16 Correct 1952 ms 6828 KB Output is correct
17 Correct 2320 ms 10524 KB Output is correct
18 Correct 2482 ms 10524 KB Output is correct
19 Correct 1523 ms 10532 KB Output is correct
20 Correct 2412 ms 10596 KB Output is correct
21 Correct 2453 ms 10520 KB Output is correct
22 Correct 1441 ms 10520 KB Output is correct
23 Correct 4591 ms 16124 KB Output is correct
24 Correct 4804 ms 15424 KB Output is correct
25 Correct 3778 ms 14900 KB Output is correct
26 Correct 5391 ms 20284 KB Output is correct
27 Correct 6005 ms 20256 KB Output is correct
28 Correct 1182 ms 6424 KB Output is correct
29 Correct 1202 ms 6152 KB Output is correct
30 Correct 1262 ms 6560 KB Output is correct
31 Correct 1133 ms 6032 KB Output is correct
32 Correct 4702 ms 20388 KB Output is correct
33 Correct 3959 ms 13032 KB Output is correct
34 Correct 5193 ms 20356 KB Output is correct
35 Correct 3234 ms 12864 KB Output is correct
36 Correct 964 ms 3960 KB Output is correct
37 Correct 5816 ms 12868 KB Output is correct
38 Correct 4807 ms 20236 KB Output is correct
39 Correct 5087 ms 20288 KB Output is correct
40 Correct 4875 ms 20360 KB Output is correct
41 Correct 7845 ms 20332 KB Output is correct
42 Correct 7835 ms 20312 KB Output is correct