oj.uz

답안 #810612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810612 2023-08-06T12:19:13 Z Khizri 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 7267 ms 13352 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=380;
        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=370;
    data1.build();
}
int update(int i, int val)
{
    arr[i+1]=val;
    tmr--;
    if(tmr==0){
        data1.build();
        tmr=370;
    }
    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 1 ms 352 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 308 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 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 1 ms 352 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 272 ms 2372 KB Output is correct
8 Correct 337 ms 2900 KB Output is correct
9 Correct 597 ms 5308 KB Output is correct
10 Correct 812 ms 5080 KB Output is correct
11 Correct 772 ms 5040 KB Output is correct
12 Correct 1101 ms 5176 KB Output is correct
13 Correct 766 ms 4892 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 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 1 ms 352 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 272 ms 2372 KB Output is correct
8 Correct 337 ms 2900 KB Output is correct
9 Correct 597 ms 5308 KB Output is correct
10 Correct 812 ms 5080 KB Output is correct
11 Correct 772 ms 5040 KB Output is correct
12 Correct 1101 ms 5176 KB Output is correct
13 Correct 766 ms 4892 KB Output is correct
14 Correct 450 ms 3632 KB Output is correct
15 Correct 570 ms 4024 KB Output is correct
16 Correct 1680 ms 5800 KB Output is correct
17 Correct 2127 ms 7216 KB Output is correct
18 Correct 2227 ms 7340 KB Output is correct
19 Correct 1585 ms 7308 KB Output is correct
20 Correct 2093 ms 7416 KB Output is correct
21 Correct 2099 ms 7316 KB Output is correct
22 Correct 1497 ms 7288 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 1 ms 352 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 272 ms 2372 KB Output is correct
8 Correct 337 ms 2900 KB Output is correct
9 Correct 597 ms 5308 KB Output is correct
10 Correct 812 ms 5080 KB Output is correct
11 Correct 772 ms 5040 KB Output is correct
12 Correct 1101 ms 5176 KB Output is correct
13 Correct 766 ms 4892 KB Output is correct
14 Correct 450 ms 3632 KB Output is correct
15 Correct 570 ms 4024 KB Output is correct
16 Correct 1680 ms 5800 KB Output is correct
17 Correct 2127 ms 7216 KB Output is correct
18 Correct 2227 ms 7340 KB Output is correct
19 Correct 1585 ms 7308 KB Output is correct
20 Correct 2093 ms 7416 KB Output is correct
21 Correct 2099 ms 7316 KB Output is correct
22 Correct 1497 ms 7288 KB Output is correct
23 Correct 6202 ms 13352 KB Output is correct
24 Correct 6345 ms 13280 KB Output is correct
25 Correct 5578 ms 11648 KB Output is correct
26 Correct 7267 ms 11680 KB Output is correct
27 Incorrect 119 ms 11604 KB Output isn't correct
28 Halted 0 ms 0 KB -