oj.uz

Submission #731053

# Submission time Handle Problem Language Result Execution time Memory
731053 2023-04-26T21:12:14 Z ogibogi2004 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 9080 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int K=333;
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();
        for(;;)
        {
            if(it==s.begin())
            {
                break;
            }
            it--;
            int t=(*it).first+cam+1;
            auto it1=s.lower_bound({t,-1});
            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-3)==0)
    {
        construct_whole();
    }
    return get_ans();
}

Compilation message

elephants.cpp: In function 'void construct_whole()':
elephants.cpp:77: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]
   77 |     for(int i=0;i<ve.size();i++)
      |                 ~^~~~~~~~~~
elephants.cpp:84: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]
   84 |     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 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 0 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 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 0 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 5535 ms 2480 KB Output is correct
8 Correct 5668 ms 4188 KB Output is correct
9 Correct 6452 ms 8680 KB Output is correct
10 Correct 6821 ms 8464 KB Output is correct
11 Correct 6979 ms 8408 KB Output is correct
12 Correct 7962 ms 8552 KB Output is correct
13 Correct 6910 ms 8260 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 0 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 5535 ms 2480 KB Output is correct
8 Correct 5668 ms 4188 KB Output is correct
9 Correct 6452 ms 8680 KB Output is correct
10 Correct 6821 ms 8464 KB Output is correct
11 Correct 6979 ms 8408 KB Output is correct
12 Correct 7962 ms 8552 KB Output is correct
13 Correct 6910 ms 8260 KB Output is correct
14 Correct 8564 ms 4924 KB Output is correct
15 Correct 8093 ms 5488 KB Output is correct
16 Execution timed out 9063 ms 9080 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 0 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 5535 ms 2480 KB Output is correct
8 Correct 5668 ms 4188 KB Output is correct
9 Correct 6452 ms 8680 KB Output is correct
10 Correct 6821 ms 8464 KB Output is correct
11 Correct 6979 ms 8408 KB Output is correct
12 Correct 7962 ms 8552 KB Output is correct
13 Correct 6910 ms 8260 KB Output is correct
14 Correct 8564 ms 4924 KB Output is correct
15 Correct 8093 ms 5488 KB Output is correct
16 Execution timed out 9063 ms 9080 KB Time limit exceeded
17 Halted 0 ms 0 KB -