oj.uz

Submission #808703

# Submission time Handle Problem Language Result Execution time Memory
808703 2023-08-05T09:38:32 Z Khizri Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 3640 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;
    int nw;
    if(arr[i]<arr[i-1]){
        int idx=i;
        while(idx>1&&arr[idx]<arr[idx-1]){
            //swap(arr[idx],arr[idx-1]);
            nw=arr[idx];
            arr[idx]=arr[idx-1];
            arr[idx-1]=nw;
            //swap(pos[idx],pos[idx-1]);
            nw=pos[idx];
            pos[idx]=pos[idx-1];
            pos[idx-1]=nw;
            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]);
            nw=arr[idx];
            arr[idx]=arr[idx+1];
            arr[idx+1]=nw;
            //swap(pos[idx],pos[idx-1]);
            nw=pos[idx];
            pos[idx]=pos[idx+1];
            pos[idx+1]=nw;
            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 1216 ms 1112 KB Output is correct
8 Correct 2220 ms 1192 KB Output is correct
9 Correct 2203 ms 1692 KB Output is correct
10 Correct 8421 ms 1692 KB Output is correct
11 Correct 8757 ms 1696 KB Output is correct
12 Correct 8272 ms 1696 KB Output is correct
13 Correct 8914 ms 1692 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 1216 ms 1112 KB Output is correct
8 Correct 2220 ms 1192 KB Output is correct
9 Correct 2203 ms 1692 KB Output is correct
10 Correct 8421 ms 1692 KB Output is correct
11 Correct 8757 ms 1696 KB Output is correct
12 Correct 8272 ms 1696 KB Output is correct
13 Correct 8914 ms 1692 KB Output is correct
14 Correct 2168 ms 2932 KB Output is correct
15 Correct 4745 ms 2928 KB Output is correct
16 Execution timed out 9042 ms 3640 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 1216 ms 1112 KB Output is correct
8 Correct 2220 ms 1192 KB Output is correct
9 Correct 2203 ms 1692 KB Output is correct
10 Correct 8421 ms 1692 KB Output is correct
11 Correct 8757 ms 1696 KB Output is correct
12 Correct 8272 ms 1696 KB Output is correct
13 Correct 8914 ms 1692 KB Output is correct
14 Correct 2168 ms 2932 KB Output is correct
15 Correct 4745 ms 2928 KB Output is correct
16 Execution timed out 9042 ms 3640 KB Time limit exceeded
17 Halted 0 ms 0 KB -