oj.uz

Submission #731058

# Submission time Handle Problem Language Result Execution time Memory
731058 2023-04-26T21:18:01 Z ogibogi2004 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 7340 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=7e4+6;
const int K=300;
int dp1[MAXN];
int dp2[MAXN];
int where[MAXN];
int where1[MAXN];
set<pair<int,int> >alle;
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()
{
    alle.clear();
    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)
    {
        alle.insert(ve[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:91: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]
   91 |     for(int i=0;i<ve.size();++i)
      |                 ~^~~~~~~~~~
elephants.cpp:98: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]
   98 |     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 1 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5306 ms 2472 KB Output is correct
8 Correct 5188 ms 3176 KB Output is correct
9 Correct 6155 ms 7108 KB Output is correct
10 Correct 6556 ms 7116 KB Output is correct
11 Correct 6967 ms 7124 KB Output is correct
12 Correct 8112 ms 7108 KB Output is correct
13 Correct 6428 ms 7108 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5306 ms 2472 KB Output is correct
8 Correct 5188 ms 3176 KB Output is correct
9 Correct 6155 ms 7108 KB Output is correct
10 Correct 6556 ms 7116 KB Output is correct
11 Correct 6967 ms 7124 KB Output is correct
12 Correct 8112 ms 7108 KB Output is correct
13 Correct 6428 ms 7108 KB Output is correct
14 Correct 7721 ms 3404 KB Output is correct
15 Correct 7446 ms 4060 KB Output is correct
16 Execution timed out 9076 ms 7340 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 5306 ms 2472 KB Output is correct
8 Correct 5188 ms 3176 KB Output is correct
9 Correct 6155 ms 7108 KB Output is correct
10 Correct 6556 ms 7116 KB Output is correct
11 Correct 6967 ms 7124 KB Output is correct
12 Correct 8112 ms 7108 KB Output is correct
13 Correct 6428 ms 7108 KB Output is correct
14 Correct 7721 ms 3404 KB Output is correct
15 Correct 7446 ms 4060 KB Output is correct
16 Execution timed out 9076 ms 7340 KB Time limit exceeded
17 Halted 0 ms 0 KB -