oj.uz

Submission #808719

# Submission time Handle Problem Language Result Execution time Memory
808719 2023-08-05T09:52:42 Z Khizri Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 1908 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=5e4+5,MAX=1e9+5;
int n,k,arr[mxn],pos[mxn],loc[mxn],nw;
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;
    }
}
void swap(int &x,int &y){
    nw=x;
    x=y;
    y=nw;
}
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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1008 ms 1100 KB Output is correct
8 Correct 2013 ms 1180 KB Output is correct
9 Correct 1390 ms 1676 KB Output is correct
10 Correct 7078 ms 1676 KB Output is correct
11 Correct 7091 ms 1680 KB Output is correct
12 Correct 7573 ms 1680 KB Output is correct
13 Correct 7235 ms 1680 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1008 ms 1100 KB Output is correct
8 Correct 2013 ms 1180 KB Output is correct
9 Correct 1390 ms 1676 KB Output is correct
10 Correct 7078 ms 1676 KB Output is correct
11 Correct 7091 ms 1680 KB Output is correct
12 Correct 7573 ms 1680 KB Output is correct
13 Correct 7235 ms 1680 KB Output is correct
14 Correct 1729 ms 1420 KB Output is correct
15 Correct 4350 ms 1500 KB Output is correct
16 Execution timed out 9075 ms 1908 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1008 ms 1100 KB Output is correct
8 Correct 2013 ms 1180 KB Output is correct
9 Correct 1390 ms 1676 KB Output is correct
10 Correct 7078 ms 1676 KB Output is correct
11 Correct 7091 ms 1680 KB Output is correct
12 Correct 7573 ms 1680 KB Output is correct
13 Correct 7235 ms 1680 KB Output is correct
14 Correct 1729 ms 1420 KB Output is correct
15 Correct 4350 ms 1500 KB Output is correct
16 Execution timed out 9075 ms 1908 KB Time limit exceeded
17 Halted 0 ms 0 KB -