oj.uz

Submission #731064

# Submission time Handle Problem Language Result Execution time Memory
731064 2023-04-26T21:25:46 Z ogibogi2004 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 6922 ms 17008 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=7e4+6;
const int K=272;
int dp1[MAXN];
int dp2[MAXN];
int where[MAXN];
int where1[MAXN];
int cam;
struct bucket
{
    set<pair<int,int> >s;
    void compute()
    {

        auto it=s.end();
        //auto ptr=it;
        //ptr--;
        for(;;)
        {
            if(it==s.begin())
            {
                break;
            }
            --it;
            int t=(*it).first+cam+1;
            auto it1=s.lower_bound({t,-1});
            /*while((*ptr).first>=t)
            {
                if(ptr==s.begin())
                {
                    ptr--;
                    break;
                }
                ptr--;
            }
            ptr++;
            auto it1=ptr;*/
            if(it1==s.end())
            {
                dp1[(*it).second]=1;
                dp2[(*it).second]=t-1;
            }
            else
            {
                dp1[(*it).second]=dp1[(*it1).second]+1;
                dp2[(*it).second]=dp2[(*it1).second];
            }
        }
    }
}b[K];
int n;
int get_ans()
{
    int T=n/K+2;
    int lastb=(n-1)/T;
    int firstnz=-1;
    for(int i=0;i<=lastb;++i)
    {
        if(b[i].s.size()==0)continue;
        firstnz=i;
        break;
    }
    int t=(*b[firstnz].s.begin()).second;
    int last=dp2[t];
    int ret=dp1[t];
    //cout<<"starting from "<<t<<endl;
    for(int i=firstnz+1;i<=lastb;++i)
    {
        if(b[i].s.size()==0)continue;
        auto it=b[i].s.lower_bound({last+1,0});
        if(it==b[i].s.end())continue;
        last=dp2[(*it).second];
        ret+=dp1[(*it).second];
    }
    return ret;
}
void construct_whole()
{
    for(int i=0;i<K;++i)b[i].s.clear();
    vector<pair<int,int> >ve;
    for(int i=1;i<=n;++i)
    {
        ve.push_back({where[i],i});
    }
    sort(ve.begin(),ve.end());
    int T=n/K+2;
    for(int i=0;i<ve.size();++i)
    {
        where[ve[i].second]=ve[i].first;
        where1[ve[i].second]=i/T;
        b[i/T].s.insert(ve[i]);
    }
    for(int i=0;i<=(ve.size()-1)/T;++i)
    {
        b[i].compute();
    }
}
void init(int N, int L, int X[])
{
    n = N;
    cam = L;
    for(int i=0;i<N;++i)
    {
        where[i+1]=X[i];
    }
    construct_whole();
}
int cnt=0;
int update(int i, int y)
{
    i++;
    int j=where1[i];
    b[j].s.erase({where[i],i});
    int T=n/K+2;
    int lastb=(n-1)/T;
    int new_j=lastb;
    if((*b[1].s.begin()).first>y)
    {
        new_j=0;
    }
    else
    {
        for(int j=1;j<lastb;++j)
        {
            if((*b[j+1].s.begin()).first>y)
            {
                new_j=j;
                break;
            }
        }
    }
    b[new_j].s.insert({y,i});
    b[new_j].compute();
    where[i]=y;
    where1[i]=new_j;
    if(j!=new_j)b[j].compute();
    ++cnt;
    if(cnt%max(1,T-1)==0)
    {
        construct_whole();
    }
    return get_ans();
}

Compilation message

elephants.cpp: In function 'void construct_whole()':
elephants.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<ve.size();++i)
      |                 ~^~~~~~~~~~
elephants.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<=(ve.size()-1)/T;++i)
      |                 ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2211 ms 2108 KB Output is correct
8 Correct 2290 ms 2424 KB Output is correct
9 Correct 2631 ms 5112 KB Output is correct
10 Correct 2982 ms 4912 KB Output is correct
11 Correct 3120 ms 4864 KB Output is correct
12 Correct 4255 ms 4780 KB Output is correct
13 Correct 3088 ms 4932 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2211 ms 2108 KB Output is correct
8 Correct 2290 ms 2424 KB Output is correct
9 Correct 2631 ms 5112 KB Output is correct
10 Correct 2982 ms 4912 KB Output is correct
11 Correct 3120 ms 4864 KB Output is correct
12 Correct 4255 ms 4780 KB Output is correct
13 Correct 3088 ms 4932 KB Output is correct
14 Correct 3967 ms 2664 KB Output is correct
15 Correct 3617 ms 3148 KB Output is correct
16 Correct 6181 ms 5020 KB Output is correct
17 Correct 6746 ms 8684 KB Output is correct
18 Correct 6922 ms 8644 KB Output is correct
19 Correct 5151 ms 8940 KB Output is correct
20 Correct 6658 ms 8400 KB Output is correct
21 Correct 6652 ms 8616 KB Output is correct
22 Correct 4583 ms 8124 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2211 ms 2108 KB Output is correct
8 Correct 2290 ms 2424 KB Output is correct
9 Correct 2631 ms 5112 KB Output is correct
10 Correct 2982 ms 4912 KB Output is correct
11 Correct 3120 ms 4864 KB Output is correct
12 Correct 4255 ms 4780 KB Output is correct
13 Correct 3088 ms 4932 KB Output is correct
14 Correct 3967 ms 2664 KB Output is correct
15 Correct 3617 ms 3148 KB Output is correct
16 Correct 6181 ms 5020 KB Output is correct
17 Correct 6746 ms 8684 KB Output is correct
18 Correct 6922 ms 8644 KB Output is correct
19 Correct 5151 ms 8940 KB Output is correct
20 Correct 6658 ms 8400 KB Output is correct
21 Correct 6652 ms 8616 KB Output is correct
22 Correct 4583 ms 8124 KB Output is correct
23 Incorrect 92 ms 17008 KB Output isn't correct
24 Halted 0 ms 0 KB -