oj.uz

Submission #887351

# Submission time Handle Problem Language Result Execution time Memory
887351 2023-12-14T09:55:36 Z abcvuitunggio Dancing Elephants (IOI11_elephants) C++17
50 / 100
 591 ms 23212 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=511,sz2=266,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?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 10584 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 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10692 KB Output is correct
6 Correct 1 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 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10692 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 269 ms 10880 KB Output is correct
8 Correct 293 ms 10920 KB Output is correct
9 Correct 357 ms 11048 KB Output is correct
10 Correct 359 ms 11060 KB Output is correct
11 Correct 333 ms 12352 KB Output is correct
12 Correct 591 ms 12776 KB Output is correct
13 Correct 334 ms 12116 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10692 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 269 ms 10880 KB Output is correct
8 Correct 293 ms 10920 KB Output is correct
9 Correct 357 ms 11048 KB Output is correct
10 Correct 359 ms 11060 KB Output is correct
11 Correct 333 ms 12352 KB Output is correct
12 Correct 591 ms 12776 KB Output is correct
13 Correct 334 ms 12116 KB Output is correct
14 Runtime error 109 ms 23212 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10692 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 269 ms 10880 KB Output is correct
8 Correct 293 ms 10920 KB Output is correct
9 Correct 357 ms 11048 KB Output is correct
10 Correct 359 ms 11060 KB Output is correct
11 Correct 333 ms 12352 KB Output is correct
12 Correct 591 ms 12776 KB Output is correct
13 Correct 334 ms 12116 KB Output is correct
14 Runtime error 109 ms 23212 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -