제출 #810573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810573		Khizri	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	0 / 100	1 ms	340 KiB

elephants

#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],clck;
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(n);
        iota(all(p),1);
        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]);
            }
            else{
                vt.back().pb(p[idx]);
            }
            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;
    }
};
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];
    }
    
}
int update(int i, int val)
{
    arr[i+1]=val;
    data1.build();
    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
*/

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In member function 'void st::build()':
elephants.cpp:41:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int id=0;id<vt.size();id++){
      |                      ~~^~~~~~~~~~
elephants.cpp: In member function 'int st::query()':
elephants.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int id=0;id<vt.size();id++){
      |                      ~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3