oj.uz

Submission #808688

# Submission time Handle Problem Language Result Execution time Memory
808688 2023-08-05T09:30:51 Z Khizri Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 3256 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],pos[mxn],loc[mxn];
void init(int N, int L, int X[])
{
    n=N,k=L;
    for(int i=1;i<=n;i++){
        arr[i]=X[i-1]+1;
        pos[i]=i;
        loc[i]=i;
    }
}
int update(int i, int y)
{
    i++,y++;
    i=loc[i];
    arr[i]=y;
    if(arr[i]<arr[i-1]){
        int idx=i;
        while(idx>1&&arr[idx]<arr[idx-1]){
            swap(arr[idx],arr[idx-1]);
            swap(pos[idx],pos[idx-1]);
            loc[pos[idx]]=idx;
            loc[pos[idx-1]]=idx-1;
            idx--;
        }
    }
    else{
        int idx=i;
        while(idx<n&&arr[idx]>arr[idx+1]){
            swap(arr[idx],arr[idx+1]);
            swap(pos[idx],pos[idx+1]);
            loc[pos[idx]]=idx;
            loc[pos[idx+1]]=idx+1;
            idx++;
        }
    }
    int ans=1;
    int left=arr[1];
    for(int i=2;i<=n;i++){
        if(arr[i]-left>k){
            ans++;
            left=arr[i];
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1235 ms 2020 KB Output is correct
8 Correct 2327 ms 2208 KB Output is correct
9 Correct 2290 ms 3256 KB Output is correct
10 Correct 8563 ms 3032 KB Output is correct
11 Correct 8821 ms 2976 KB Output is correct
12 Correct 8301 ms 3124 KB Output is correct
13 Execution timed out 9018 ms 2832 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1235 ms 2020 KB Output is correct
8 Correct 2327 ms 2208 KB Output is correct
9 Correct 2290 ms 3256 KB Output is correct
10 Correct 8563 ms 3032 KB Output is correct
11 Correct 8821 ms 2976 KB Output is correct
12 Correct 8301 ms 3124 KB Output is correct
13 Execution timed out 9018 ms 2832 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1235 ms 2020 KB Output is correct
8 Correct 2327 ms 2208 KB Output is correct
9 Correct 2290 ms 3256 KB Output is correct
10 Correct 8563 ms 3032 KB Output is correct
11 Correct 8821 ms 2976 KB Output is correct
12 Correct 8301 ms 3124 KB Output is correct
13 Execution timed out 9018 ms 2832 KB Time limit exceeded
14 Halted 0 ms 0 KB -