oj.uz

Submission #68498

# Submission time Handle Problem Language Result Execution time Memory
68498 2018-08-17T08:26:10 Z losmi247 Secret (JOI14_secret) C++14
30 / 100
 804 ms 5540 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
int Q,l,r;
int drvo[2000005];
int n,a[2000005];
typedef pair <int,int> p;
map <p,int> mapa;
int secret(int x,int y){
    if(mapa.count(p(x,y))){
        return mapa[p(x,y)];
    }
    return mapa[p(x,y)] = Secret(x,y);
}
void update(int i,int j,int poz,int val,int node){
    if(i == j){
        drvo[node] = val;
        return;
    }
    int mid = i+(j-i)/2;
    if(poz <= mid){
        update(i,mid,poz,val,2*node+1);
    }
    else{
        update(mid+1,j,poz,val,2*node+2);
    }
    drvo[node] = secret(drvo[2*node+1],drvo[2*node+2]);
}
void build(int i,int j,int node){
    if(i == j){
        drvo[node] = a[i];
        return;
    }
    int mid = i+(j-i)/2;
    build(i,mid,2*node+1);
    build(mid+1,j,2*node+2);
    drvo[node] = secret(drvo[2*node+1],drvo[2*node+2]);
}
int get(int i,int j,int l,int r,int node){
    if(j < l || i > r){
        return -1;
    }
    if(l <= i && r >= j){
        return drvo[node];
    }
    int mid = i+(j-i)/2;
    int p1 = get(i,mid,l,r,2*node+1),p2=get(mid+1,j,l,r,2*node+2);
    if(p1 == -1){
        return p2;
    }
    else if(p2 == -1){
        return p1;
    }
    else{
        return secret(get(i,mid,l,r,2*node+1),get(mid+1,j,l,r,2*node+2));
    }
}
int Query(int L,int R){
    return get(0,n-1,L,R,0);
}
void Init(int N,int A[]){
    n = N;
    for(int i = 0; i < N; i++){
        //update(0,n-1,i,A[i],0);
        a[i] = A[i];
    }
    build(0,n-1,0);
    cin >> Q;
    while(Q--){
        cin >> l >> r;
        cout << Query(l,r) << endl;
    }
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 235 ms 3380 KB Output is partially correct - number of calls to Secret by Init = 510, maximum number of calls to Secret by Query = 10
2 Partially correct 237 ms 3380 KB Output is partially correct - number of calls to Secret by Init = 511, maximum number of calls to Secret by Query = 12
3 Partially correct 257 ms 3380 KB Output is partially correct - number of calls to Secret by Init = 512, maximum number of calls to Secret by Query = 11
4 Partially correct 740 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 998, maximum number of calls to Secret by Query = 13
5 Partially correct 727 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13
6 Partially correct 630 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 4
7 Partially correct 803 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
8 Partially correct 804 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 15
9 Partially correct 803 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 14
10 Partially correct 796 ms 5540 KB Output is partially correct - number of calls to Secret by Init = 999, maximum number of calls to Secret by Query = 13