oj.uz

Submission #887344

# Submission time Handle Problem Language Result Execution time Memory
887344 2023-12-14T09:39:06 Z abcvuitunggio Dancing Elephants (IOI11_elephants) C++17
26 / 100
 14 ms 12344 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;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;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){
        x[i]=y;
        reinit();
    }
    else{
        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,pos[cur]+1);
        while (j<=(n-1)/sz){
            if (v[j].empty()||x[v[j].back()]>x[cur]+l){
                j++;
                continue;
            }
            break;
        }
        if (j>(n-1)/sz)
            break;
        int l=0,r=v[j].size()-1,kq=-1;
        while (l<=r){
            int mid=(l+r)>>1;
            if (x[v[j][mid]]>x[cur]+l){
                kq=mid;
                r=mid-1;
            }
            else
                l=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 10588 KB Output is correct
2 Correct 2 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 10588 KB Output is correct
2 Correct 2 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 1 ms 10696 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 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 1 ms 10696 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Incorrect 14 ms 12344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 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 1 ms 10696 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Incorrect 14 ms 12344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 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 1 ms 10696 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Incorrect 14 ms 12344 KB Output isn't correct
8 Halted 0 ms 0 KB -