oj.uz

답안 #810582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810582 2023-08-06T11:36:08 Z Khizri 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 2272 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],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;
        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]);
            }
            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
*/

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Execution timed out 9028 ms 2272 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Execution timed out 9028 ms 2272 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Execution timed out 9028 ms 2272 KB Time limit exceeded
8 Halted 0 ms 0 KB -