oj.uz

Submission #887365

# Submission time Handle Problem Language Result Execution time Memory
887365 2023-12-14T10:06:16 Z abcvuitunggio Dancing Elephants (IOI11_elephants) C++17
100 / 100
 3536 ms 19064 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=300,sz2=299,maxN=150000;
int n,l,x[maxN+1],idx[maxN+1],q,pos[maxN+1];
pair <int, int> nxt[maxN/sz+1][sz+sz2+1];
vector <int> v[maxN/sz+1];
void calc(int k){
    if (v[k].empty())
        return;
    int j=v[k].size()-1;
    for (int i=j;i>=0;i--){
        while (x[v[k][i]]+l<x[v[k][j]])
            j--;
        if (j==v[k].size()-1)
            nxt[k][i]={i,0};
        else{
            j++;
            nxt[k][i]={nxt[k][j].first,nxt[k][j].second+1};
        }
    }
}
void init(int N, int L, int X[]){
    n=N,l=L;
    for (int i=0;i<n;i++){
        x[i]=X[i];
        idx[i]=i;
    }
    sort(idx,idx+n,[](int i, int j){return x[i]<x[j];});
    for (int i=0;i*sz<n;i++){
        v[i].clear();
        for (int j=i*sz;j<min(i*sz+sz,n);j++){
            v[i].push_back(idx[j]);
            pos[idx[j]]=i;
        }
        calc(i);
    }
}
void reinit(){
    int j=0;
    for (int i=0;i*sz<n;i++){
        for (int k:v[i]){
            idx[j]=k;
            j++;
        }
    }
    for (int i=0;i*sz<n;i++){
        v[i].clear();
        for (int j=i*sz;j<min(i*sz+sz,n);j++){
            v[i].push_back(idx[j]);
            pos[idx[j]]=i;
        }
        calc(i);
    }
}
int update(int i, int y){
    q++;
    if (q%sz2==0)
        reinit();
    vector <int> tmp;
    int c=0;
    for (int j:v[pos[i]]){
        if (j!=i||c)
            tmp.push_back(j);
        else
            c=1;
    }
    swap(tmp,v[pos[i]]);
    calc(pos[i]);
    tmp.clear();
    x[i]=y;
    int newpos=-1;
    for (int j=0;j*sz<n;j++){
        int l=(j?x[v[j-1].back()]:-1),r=(j*sz+sz<n&&!v[j+1].empty()?x[v[j+1][0]]:1000000001);
        if (l<=y&&y<=r){
            newpos=j;
            break;
        }
    }
    pos[i]=newpos;
    c=0;
    for (int j:v[newpos]){
        if (x[j]>=y&&!c){
            tmp.push_back(i);
            c=1;
        }
        tmp.push_back(j);
    }
    if (!c)
        tmp.push_back(i);
    swap(v[newpos],tmp);
    calc(newpos);
    int j=0,cur=0,res=0,block=0;
    while (true){
        res+=nxt[block][cur].second;
        cur=nxt[block][cur].first;
        res++;
        j=max(j,block+1);
        while (j<=(n-1)/sz){
            if (v[j].empty()||x[v[j].back()]<=x[v[block][cur]]+l){
                j++;
                continue;
            }
            break;
        }
        if (j>(n-1)/sz)
            break;
        int lo=0,hi=v[j].size()-1,kq=-1;
        while (lo<=hi){
            int mid=(lo+hi)>>1;
            if (x[v[j][mid]]>x[v[block][cur]]+l){
                kq=mid;
                hi=mid-1;
            }
            else
                lo=mid+1;
        }
        cur=kq;
        block=j;
    }
    return res;
}

Compilation message

elephants.cpp: In function 'void calc(int)':
elephants.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if (j==v[k].size()-1)
      |             ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 199 ms 13136 KB Output is correct
8 Correct 215 ms 12888 KB Output is correct
9 Correct 304 ms 13140 KB Output is correct
10 Correct 310 ms 13260 KB Output is correct
11 Correct 252 ms 13248 KB Output is correct
12 Correct 482 ms 13240 KB Output is correct
13 Correct 306 ms 13244 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 199 ms 13136 KB Output is correct
8 Correct 215 ms 12888 KB Output is correct
9 Correct 304 ms 13140 KB Output is correct
10 Correct 310 ms 13260 KB Output is correct
11 Correct 252 ms 13248 KB Output is correct
12 Correct 482 ms 13240 KB Output is correct
13 Correct 306 ms 13244 KB Output is correct
14 Correct 252 ms 13096 KB Output is correct
15 Correct 353 ms 12892 KB Output is correct
16 Correct 773 ms 13148 KB Output is correct
17 Correct 868 ms 13396 KB Output is correct
18 Correct 929 ms 13372 KB Output is correct
19 Correct 519 ms 13520 KB Output is correct
20 Correct 852 ms 13512 KB Output is correct
21 Correct 817 ms 13376 KB Output is correct
22 Correct 507 ms 13144 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 199 ms 13136 KB Output is correct
8 Correct 215 ms 12888 KB Output is correct
9 Correct 304 ms 13140 KB Output is correct
10 Correct 310 ms 13260 KB Output is correct
11 Correct 252 ms 13248 KB Output is correct
12 Correct 482 ms 13240 KB Output is correct
13 Correct 306 ms 13244 KB Output is correct
14 Correct 252 ms 13096 KB Output is correct
15 Correct 353 ms 12892 KB Output is correct
16 Correct 773 ms 13148 KB Output is correct
17 Correct 868 ms 13396 KB Output is correct
18 Correct 929 ms 13372 KB Output is correct
19 Correct 519 ms 13520 KB Output is correct
20 Correct 852 ms 13512 KB Output is correct
21 Correct 817 ms 13376 KB Output is correct
22 Correct 507 ms 13144 KB Output is correct
23 Correct 2863 ms 18012 KB Output is correct
24 Correct 2868 ms 18260 KB Output is correct
25 Correct 2350 ms 18004 KB Output is correct
26 Correct 2671 ms 18020 KB Output is correct
27 Correct 2496 ms 18104 KB Output is correct
28 Correct 844 ms 14888 KB Output is correct
29 Correct 795 ms 15056 KB Output is correct
30 Correct 840 ms 14936 KB Output is correct
31 Correct 805 ms 14884 KB Output is correct
32 Correct 1822 ms 18028 KB Output is correct
33 Correct 1658 ms 18032 KB Output is correct
34 Correct 2455 ms 18020 KB Output is correct
35 Correct 1550 ms 19064 KB Output is correct
36 Correct 842 ms 18256 KB Output is correct
37 Correct 3098 ms 18036 KB Output is correct
38 Correct 2564 ms 18024 KB Output is correct
39 Correct 2280 ms 18028 KB Output is correct
40 Correct 2429 ms 18004 KB Output is correct
41 Correct 3529 ms 18024 KB Output is correct
42 Correct 3536 ms 18020 KB Output is correct