oj.uz

Submission #731060

# Submission time Handle Problem Language Result Execution time Memory
731060 2023-04-26T21:23:16 Z ogibogi2004 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 7348 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=7e4+6;
const int K=280;
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 0 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 0 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 2 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 0 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 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4502 ms 2468 KB Output is correct
8 Correct 4772 ms 3172 KB Output is correct
9 Correct 5283 ms 7112 KB Output is correct
10 Correct 5524 ms 7240 KB Output is correct
11 Correct 5652 ms 7116 KB Output is correct
12 Correct 6645 ms 7240 KB Output is correct
13 Correct 5484 ms 7216 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4502 ms 2468 KB Output is correct
8 Correct 4772 ms 3172 KB Output is correct
9 Correct 5283 ms 7112 KB Output is correct
10 Correct 5524 ms 7240 KB Output is correct
11 Correct 5652 ms 7116 KB Output is correct
12 Correct 6645 ms 7240 KB Output is correct
13 Correct 5484 ms 7216 KB Output is correct
14 Correct 6853 ms 3404 KB Output is correct
15 Correct 6520 ms 4068 KB Output is correct
16 Execution timed out 9019 ms 7348 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 4502 ms 2468 KB Output is correct
8 Correct 4772 ms 3172 KB Output is correct
9 Correct 5283 ms 7112 KB Output is correct
10 Correct 5524 ms 7240 KB Output is correct
11 Correct 5652 ms 7116 KB Output is correct
12 Correct 6645 ms 7240 KB Output is correct
13 Correct 5484 ms 7216 KB Output is correct
14 Correct 6853 ms 3404 KB Output is correct
15 Correct 6520 ms 4068 KB Output is correct
16 Execution timed out 9019 ms 7348 KB Time limit exceeded
17 Halted 0 ms 0 KB -