oj.uz

답안 #810605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810605 2023-08-06T12:07:24 Z Khizri 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 6391 ms 13136 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*2+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=-5;
        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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 412 ms 2316 KB Output is correct
8 Correct 480 ms 2700 KB Output is correct
9 Correct 860 ms 4572 KB Output is correct
10 Correct 1078 ms 4184 KB Output is correct
11 Correct 1094 ms 4268 KB Output is correct
12 Correct 1492 ms 4256 KB Output is correct
13 Correct 1118 ms 3944 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 412 ms 2316 KB Output is correct
8 Correct 480 ms 2700 KB Output is correct
9 Correct 860 ms 4572 KB Output is correct
10 Correct 1078 ms 4184 KB Output is correct
11 Correct 1094 ms 4268 KB Output is correct
12 Correct 1492 ms 4256 KB Output is correct
13 Correct 1118 ms 3944 KB Output is correct
14 Correct 771 ms 3436 KB Output is correct
15 Correct 841 ms 3516 KB Output is correct
16 Correct 2201 ms 4872 KB Output is correct
17 Correct 2545 ms 6212 KB Output is correct
18 Correct 2658 ms 6144 KB Output is correct
19 Correct 1939 ms 6344 KB Output is correct
20 Correct 2643 ms 6212 KB Output is correct
21 Correct 2552 ms 6176 KB Output is correct
22 Correct 1835 ms 5872 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 412 ms 2316 KB Output is correct
8 Correct 480 ms 2700 KB Output is correct
9 Correct 860 ms 4572 KB Output is correct
10 Correct 1078 ms 4184 KB Output is correct
11 Correct 1094 ms 4268 KB Output is correct
12 Correct 1492 ms 4256 KB Output is correct
13 Correct 1118 ms 3944 KB Output is correct
14 Correct 771 ms 3436 KB Output is correct
15 Correct 841 ms 3516 KB Output is correct
16 Correct 2201 ms 4872 KB Output is correct
17 Correct 2545 ms 6212 KB Output is correct
18 Correct 2658 ms 6144 KB Output is correct
19 Correct 1939 ms 6344 KB Output is correct
20 Correct 2643 ms 6212 KB Output is correct
21 Correct 2552 ms 6176 KB Output is correct
22 Correct 1835 ms 5872 KB Output is correct
23 Correct 5485 ms 13136 KB Output is correct
24 Correct 5650 ms 13104 KB Output is correct
25 Correct 4762 ms 13136 KB Output is correct
26 Correct 6391 ms 13112 KB Output is correct
27 Incorrect 205 ms 12960 KB Output isn't correct
28 Halted 0 ms 0 KB -