oj.uz

Submission #887357

# Submission time Handle Problem Language Result Execution time Memory
887357 2023-12-14T09:58:50 Z abcvuitunggio Dancing Elephants (IOI11_elephants) C++17
26 / 100
 305 ms 26208 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=400,maxN=150000;
int n,l,x[maxN+1],idx[maxN+1],q,pos[maxN+1];
pair <int, int> nxt[maxN/sz+1][sz*2+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%sz==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 2 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 2 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 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 224 ms 12888 KB Output is correct
8 Correct 245 ms 12992 KB Output is correct
9 Correct 305 ms 13136 KB Output is correct
10 Runtime error 30 ms 26208 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 224 ms 12888 KB Output is correct
8 Correct 245 ms 12992 KB Output is correct
9 Correct 305 ms 13136 KB Output is correct
10 Runtime error 30 ms 26208 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 224 ms 12888 KB Output is correct
8 Correct 245 ms 12992 KB Output is correct
9 Correct 305 ms 13136 KB Output is correct
10 Runtime error 30 ms 26208 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -