oj.uz

Submission #810618

# Submission time Handle Problem Language Result Execution time Memory
810618 2023-08-06T12:26:46 Z Khizri Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7416 ms 16236 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5,MAX=1e9+5;
int n,k,arr[mxn],sz,block,loc[mxn],pos[mxn],tmr;
bool cmp(int i,int j){
    return arr[i]<arr[j];
}
struct st{
    vector<vector<int>>vt,last,dis;
    void build(){
        vt.clear(),last.clear(),dis.clear();
        vector<int>p;
        for(int i=1;i<=n;i++){
            p.pb(i);
        }
        sort(all(p),cmp);
        int sz=500;
        int idx=0,say=0;
        while(idx<n){
            say++;
            if(say==1){
                vt.pb({});
                vt.back().pb(p[idx]);
                loc[p[idx]]=vt.size()-1;
            }
            else{
                vt.back().pb(p[idx]);
                loc[p[idx]]=vt.size()-1;
            }
            idx++;
            if(say>=sz) say=0;
        }
        for(int id=0;id<vt.size();id++){
            vector<int>vx(sz*5+5);
            last.pb(vx);
            dis.pb(vx);
            int idx=vt[id].size()-1;
            for(int i=vt[id].size()-1;i>=0;i--){
                while(idx-1>=0&&arr[vt[id][i]]+k<arr[vt[id][idx-1]]){
                    idx--;
                }
                if(arr[vt[id][i]]+k>=arr[vt[id][idx]]){
                    last[id][i]=arr[vt[id][i]]+k+1;
                    dis[id][i]=1;
                }
                else{
                    last[id][i]=last[id][idx];
                    dis[id][i]=dis[id][idx]+1;
                }
            }
        }
    }
    int query(){
        int left=-MAX;
        int ans=0;
        for(int id=0;id<vt.size();id++){
            int l=0,r=vt[id].size()-1;
            int res=-1;
            while(l<=r){
                int m=(l+r)/2;
                if(arr[vt[id][m]]>=left){
                    r=m-1;
                    res=m;
                }
                else{
                    l=m+1;
                }
            }
            if(res==-1) continue;
            left=last[id][res];
            ans+=dis[id][res];
        }
        return ans;
    }
    void del(int idx){
        int row=loc[idx];
        for(int i=0;i<vt[row].size();i++){
            if(vt[row][i]==idx){
                vt[row].erase(vt[row].begin()+i);
                break;
            }
        }
        int id=row;
        idx=vt[id].size()-1;
        for(int i=vt[id].size()-1;i>=0;i--){
            while(idx-1>=0&&arr[vt[id][i]]+k<arr[vt[id][idx-1]]){
                idx--;
            }
            if(arr[vt[id][i]]+k>=arr[vt[id][idx]]){
                last[id][i]=arr[vt[id][i]]+k+1;
                dis[id][i]=1;
            }
            else{
                last[id][i]=last[id][idx];
                dis[id][i]=dis[id][idx]+1;
            }
        }
    }
    void add(int idx){
        int row=0;
        for(int i=vt.size()-1;i>=0;i--){
            if(arr[vt[i][0]]<=arr[idx]){
                row=i;
                break;
            }
        }
        loc[idx]=row;
        bool ok=true;
        for(int i=0;i<vt[row].size();i++){
            if(arr[vt[row][i]]>arr[idx]){
                vt[row].insert(vt[row].begin()+i,idx);
                ok=false;
                break;
            }
        }
        if(ok){
            vt[row].pb(idx);
        }
        int id=row;
        idx=vt[id].size()-1;
        for(int i=vt[id].size()-1;i>=0;i--){
            while(idx-1>=0&&arr[vt[id][i]]+k<arr[vt[id][idx-1]]){
                idx--;
            }
            if(arr[vt[id][i]]+k>=arr[vt[id][idx]]){
                last[id][i]=arr[vt[id][i]]+k+1;
                dis[id][i]=1;
            }
            else{
                last[id][i]=last[id][idx];
                dis[id][i]=dis[id][idx]+1;
            }
        }
    }
};
st data1;
void init(int N, int L, int X[])
{
    n=N,k=L;
    for(int i=1;i<=n;i++){
        arr[i]=X[i-1];
    }
    tmr=490;
    data1.build();
}
int update(int i, int val)
{
    arr[i+1]=val;
    tmr--;
    if(tmr==0){
        data1.build();
        tmr=490;
    }
    else{
        data1.del(i+1);
        arr[i+1]=val;
        data1.add(i+1);
    }
    return data1.query();
}
/*
g++ elephants.cpp grader.cpp ; .\a.exe
10 10 0
1 3 7 15 27 37 46 90 98 100
4 10 5 
10 15 17 20
2 16 1
1 25 2
3 25 2
0 38 2
2 0 3
*/

Compilation message

elephants.cpp: In member function 'void st::build()':
elephants.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int id=0;id<vt.size();id++){
      |                      ~~^~~~~~~~~~
elephants.cpp: In member function 'int st::query()':
elephants.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int id=0;id<vt.size();id++){
      |                      ~~^~~~~~~~~~
elephants.cpp: In member function 'void st::del(int)':
elephants.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int i=0;i<vt[row].size();i++){
      |                     ~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void st::add(int)':
elephants.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int i=0;i<vt[row].size();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 0 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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 313 ms 1716 KB Output is correct
8 Correct 330 ms 2048 KB Output is correct
9 Correct 547 ms 4052 KB Output is correct
10 Correct 694 ms 4024 KB Output is correct
11 Correct 682 ms 3980 KB Output is correct
12 Correct 995 ms 4036 KB Output is correct
13 Correct 680 ms 3924 KB Output is correct

Subtask #4
47.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 313 ms 1716 KB Output is correct
8 Correct 330 ms 2048 KB Output is correct
9 Correct 547 ms 4052 KB Output is correct
10 Correct 694 ms 4024 KB Output is correct
11 Correct 682 ms 3980 KB Output is correct
12 Correct 995 ms 4036 KB Output is correct
13 Correct 680 ms 3924 KB Output is correct
14 Correct 439 ms 2296 KB Output is correct
15 Correct 556 ms 2720 KB Output is correct
16 Correct 1574 ms 4252 KB Output is correct
17 Correct 1798 ms 5568 KB Output is correct
18 Correct 1870 ms 5572 KB Output is correct
19 Correct 1259 ms 5568 KB Output is correct
20 Correct 1791 ms 5572 KB Output is correct
21 Correct 1726 ms 5580 KB Output is correct
22 Correct 1236 ms 5456 KB Output is correct

Subtask #5
3.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 313 ms 1716 KB Output is correct
8 Correct 330 ms 2048 KB Output is correct
9 Correct 547 ms 4052 KB Output is correct
10 Correct 694 ms 4024 KB Output is correct
11 Correct 682 ms 3980 KB Output is correct
12 Correct 995 ms 4036 KB Output is correct
13 Correct 680 ms 3924 KB Output is correct
14 Correct 439 ms 2296 KB Output is correct
15 Correct 556 ms 2720 KB Output is correct
16 Correct 1574 ms 4252 KB Output is correct
17 Correct 1798 ms 5568 KB Output is correct
18 Correct 1870 ms 5572 KB Output is correct
19 Correct 1259 ms 5568 KB Output is correct
20 Correct 1791 ms 5572 KB Output is correct
21 Correct 1726 ms 5580 KB Output is correct
22 Correct 1236 ms 5456 KB Output is correct
23 Correct 4533 ms 11444 KB Output is correct
24 Correct 4751 ms 11432 KB Output is correct
25 Correct 3896 ms 11696 KB Output is correct
26 Correct 5199 ms 11692 KB Output is correct
27 Correct 5764 ms 11564 KB Output is correct
28 Correct 1520 ms 2408 KB Output is correct
29 Correct 1440 ms 2608 KB Output is correct
30 Correct 1516 ms 2528 KB Output is correct
31 Correct 1435 ms 2632 KB Output is correct
32 Correct 5471 ms 11444 KB Output is correct
33 Correct 5472 ms 11444 KB Output is correct
34 Correct 5376 ms 11436 KB Output is correct
35 Correct 4324 ms 11440 KB Output is correct
36 Correct 2954 ms 11444 KB Output is correct
37 Correct 6766 ms 11440 KB Output is correct
38 Correct 5373 ms 11436 KB Output is correct
39 Correct 5528 ms 11432 KB Output is correct
40 Correct 5356 ms 11492 KB Output is correct
41 Correct 7225 ms 11436 KB Output is correct
42 Correct 7416 ms 16236 KB Output is correct