oj.uz

Submission #887361

# Submission time Handle Problem Language Result Execution time Memory
887361 2023-12-14T10:01:16 Z abcvuitunggio Dancing Elephants (IOI11_elephants) C++17
100 / 100
 4086 ms 12136 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=1021,sz2=376,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 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 455 ms 10844 KB Output is correct
8 Correct 463 ms 11092 KB Output is correct
9 Correct 472 ms 10840 KB Output is correct
10 Correct 481 ms 11092 KB Output is correct
11 Correct 465 ms 11096 KB Output is correct
12 Correct 867 ms 11348 KB Output is correct
13 Correct 468 ms 11068 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 455 ms 10844 KB Output is correct
8 Correct 463 ms 11092 KB Output is correct
9 Correct 472 ms 10840 KB Output is correct
10 Correct 481 ms 11092 KB Output is correct
11 Correct 465 ms 11096 KB Output is correct
12 Correct 867 ms 11348 KB Output is correct
13 Correct 468 ms 11068 KB Output is correct
14 Correct 597 ms 11092 KB Output is correct
15 Correct 696 ms 10964 KB Output is correct
16 Correct 1572 ms 11412 KB Output is correct
17 Correct 1467 ms 11508 KB Output is correct
18 Correct 1601 ms 11348 KB Output is correct
19 Correct 594 ms 11148 KB Output is correct
20 Correct 1469 ms 11256 KB Output is correct
21 Correct 1350 ms 11668 KB Output is correct
22 Correct 587 ms 11096 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 455 ms 10844 KB Output is correct
8 Correct 463 ms 11092 KB Output is correct
9 Correct 472 ms 10840 KB Output is correct
10 Correct 481 ms 11092 KB Output is correct
11 Correct 465 ms 11096 KB Output is correct
12 Correct 867 ms 11348 KB Output is correct
13 Correct 468 ms 11068 KB Output is correct
14 Correct 597 ms 11092 KB Output is correct
15 Correct 696 ms 10964 KB Output is correct
16 Correct 1572 ms 11412 KB Output is correct
17 Correct 1467 ms 11508 KB Output is correct
18 Correct 1601 ms 11348 KB Output is correct
19 Correct 594 ms 11148 KB Output is correct
20 Correct 1469 ms 11256 KB Output is correct
21 Correct 1350 ms 11668 KB Output is correct
22 Correct 587 ms 11096 KB Output is correct
23 Correct 2470 ms 11448 KB Output is correct
24 Correct 2725 ms 11452 KB Output is correct
25 Correct 1883 ms 11448 KB Output is correct
26 Correct 2129 ms 11476 KB Output is correct
27 Correct 2028 ms 11464 KB Output is correct
28 Correct 2238 ms 10788 KB Output is correct
29 Correct 2200 ms 10792 KB Output is correct
30 Correct 2229 ms 10796 KB Output is correct
31 Correct 2195 ms 10944 KB Output is correct
32 Correct 2049 ms 11464 KB Output is correct
33 Correct 1572 ms 11716 KB Output is correct
34 Correct 1876 ms 11468 KB Output is correct
35 Correct 1738 ms 12136 KB Output is correct
36 Correct 1331 ms 11604 KB Output is correct
37 Correct 2729 ms 11756 KB Output is correct
38 Correct 1843 ms 11460 KB Output is correct
39 Correct 1814 ms 11464 KB Output is correct
40 Correct 1839 ms 11464 KB Output is correct
41 Correct 3988 ms 11852 KB Output is correct
42 Correct 4086 ms 12104 KB Output is correct