oj.uz

Submission #887359

# Submission time Handle Problem Language Result Execution time Memory
887359 2023-12-14T09:59:35 Z abcvuitunggio Dancing Elephants (IOI11_elephants) C++17
100 / 100
 3340 ms 18452 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=400,sz2=399,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 8540 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 8540 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 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 237 ms 12980 KB Output is correct
8 Correct 249 ms 12992 KB Output is correct
9 Correct 308 ms 13148 KB Output is correct
10 Correct 319 ms 13172 KB Output is correct
11 Correct 284 ms 13176 KB Output is correct
12 Correct 503 ms 13392 KB Output is correct
13 Correct 308 ms 13144 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 237 ms 12980 KB Output is correct
8 Correct 249 ms 12992 KB Output is correct
9 Correct 308 ms 13148 KB Output is correct
10 Correct 319 ms 13172 KB Output is correct
11 Correct 284 ms 13176 KB Output is correct
12 Correct 503 ms 13392 KB Output is correct
13 Correct 308 ms 13144 KB Output is correct
14 Correct 307 ms 13056 KB Output is correct
15 Correct 394 ms 12888 KB Output is correct
16 Correct 852 ms 13156 KB Output is correct
17 Correct 905 ms 13516 KB Output is correct
18 Correct 984 ms 13272 KB Output is correct
19 Correct 513 ms 13136 KB Output is correct
20 Correct 929 ms 13268 KB Output is correct
21 Correct 888 ms 13280 KB Output is correct
22 Correct 561 ms 13144 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 237 ms 12980 KB Output is correct
8 Correct 249 ms 12992 KB Output is correct
9 Correct 308 ms 13148 KB Output is correct
10 Correct 319 ms 13172 KB Output is correct
11 Correct 284 ms 13176 KB Output is correct
12 Correct 503 ms 13392 KB Output is correct
13 Correct 308 ms 13144 KB Output is correct
14 Correct 307 ms 13056 KB Output is correct
15 Correct 394 ms 12888 KB Output is correct
16 Correct 852 ms 13156 KB Output is correct
17 Correct 905 ms 13516 KB Output is correct
18 Correct 984 ms 13272 KB Output is correct
19 Correct 513 ms 13136 KB Output is correct
20 Correct 929 ms 13268 KB Output is correct
21 Correct 888 ms 13280 KB Output is correct
22 Correct 561 ms 13144 KB Output is correct
23 Correct 2618 ms 17768 KB Output is correct
24 Correct 2838 ms 17768 KB Output is correct
25 Correct 1966 ms 17608 KB Output is correct
26 Correct 2316 ms 17776 KB Output is correct
27 Correct 2149 ms 17784 KB Output is correct
28 Correct 1230 ms 14892 KB Output is correct
29 Correct 1100 ms 14888 KB Output is correct
30 Correct 1122 ms 14892 KB Output is correct
31 Correct 1089 ms 15064 KB Output is correct
32 Correct 1666 ms 17784 KB Output is correct
33 Correct 1490 ms 17780 KB Output is correct
34 Correct 2103 ms 17784 KB Output is correct
35 Correct 1408 ms 18452 KB Output is correct
36 Correct 828 ms 17776 KB Output is correct
37 Correct 2528 ms 17796 KB Output is correct
38 Correct 2292 ms 17784 KB Output is correct
39 Correct 1895 ms 17780 KB Output is correct
40 Correct 2136 ms 17780 KB Output is correct
41 Correct 3340 ms 17784 KB Output is correct
42 Correct 3119 ms 17744 KB Output is correct