oj.uz

Submission #810608

# Submission time Handle Problem Language Result Execution time Memory
810608 2023-08-06T12:12:03 Z Khizri Dancing Elephants (IOI11_elephants) C++17
97 / 100
 6838 ms 12204 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=sqrt(n);
        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=max((int)sqrt(n)-1,1);
    data1.build();
}
int update(int i, int val)
{
    arr[i+1]=val;
    tmr--;
    if(tmr==0){
        data1.build();
        tmr=max((int)sqrt(n)-1,1);
    }
    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 1 ms 308 KB Output is correct
3 Correct 0 ms 308 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 308 KB Output is correct
3 Correct 0 ms 308 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 1 ms 308 KB Output is correct
3 Correct 0 ms 308 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 448 ms 2584 KB Output is correct
8 Correct 499 ms 3008 KB Output is correct
9 Correct 895 ms 5028 KB Output is correct
10 Correct 1146 ms 5076 KB Output is correct
11 Correct 1115 ms 4936 KB Output is correct
12 Correct 1530 ms 5016 KB Output is correct
13 Correct 1153 ms 4896 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 1 ms 308 KB Output is correct
3 Correct 0 ms 308 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 448 ms 2584 KB Output is correct
8 Correct 499 ms 3008 KB Output is correct
9 Correct 895 ms 5028 KB Output is correct
10 Correct 1146 ms 5076 KB Output is correct
11 Correct 1115 ms 4936 KB Output is correct
12 Correct 1530 ms 5016 KB Output is correct
13 Correct 1153 ms 4896 KB Output is correct
14 Correct 780 ms 3256 KB Output is correct
15 Correct 867 ms 3728 KB Output is correct
16 Correct 2306 ms 4932 KB Output is correct
17 Correct 2619 ms 6232 KB Output is correct
18 Correct 2682 ms 6112 KB Output is correct
19 Correct 1934 ms 6116 KB Output is correct
20 Correct 2584 ms 6128 KB Output is correct
21 Correct 2668 ms 6100 KB Output is correct
22 Correct 1885 ms 6104 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 308 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 448 ms 2584 KB Output is correct
8 Correct 499 ms 3008 KB Output is correct
9 Correct 895 ms 5028 KB Output is correct
10 Correct 1146 ms 5076 KB Output is correct
11 Correct 1115 ms 4936 KB Output is correct
12 Correct 1530 ms 5016 KB Output is correct
13 Correct 1153 ms 4896 KB Output is correct
14 Correct 780 ms 3256 KB Output is correct
15 Correct 867 ms 3728 KB Output is correct
16 Correct 2306 ms 4932 KB Output is correct
17 Correct 2619 ms 6232 KB Output is correct
18 Correct 2682 ms 6112 KB Output is correct
19 Correct 1934 ms 6116 KB Output is correct
20 Correct 2584 ms 6128 KB Output is correct
21 Correct 2668 ms 6100 KB Output is correct
22 Correct 1885 ms 6104 KB Output is correct
23 Correct 6003 ms 12204 KB Output is correct
24 Correct 6203 ms 12056 KB Output is correct
25 Correct 5390 ms 11988 KB Output is correct
26 Correct 6838 ms 12116 KB Output is correct
27 Incorrect 210 ms 11916 KB Output isn't correct
28 Halted 0 ms 0 KB -