oj.uz

Submission #540768

# Submission time Handle Problem Language Result Execution time Memory
540768 2022-03-21T17:09:38 Z Wael Secret (JOI14_secret) C++14
0 / 100
 20000 ms 4348 KB 
#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define endl '\n'
int const M = (1 << 10);
set<pair<pair<ll , ll> , ll>>st;
ll val , size = 1 , l , r , t , x , y , n , m , s[M];
vector<ll>sum , op;
vector<ll>elem[3][M];

inline ll Ask(int x , int y) {
  return Secret(x , y);
}

inline void Build(int x , int lx , int rx) {
     int mid = (rx - lx + 1) / 2;

     elem[1][x].push_back(s[mid]);

     for(int i = mid - 1 ; i >= lx ; --i) {
        ll res = Ask(s[i] , elem[1][x].back());
        elem[1][x].push_back(res);
     }
     reverse(elem[1][x].begin() , elem[1][x].end());

     elem[2][x].push_back(s[mid + 1]);
     for(int i = mid + 2 ; i <= rx ; ++i) {
        ll res = Ask(s[i] , elem[2][x].back());
     }
}

inline ll Get(int l , int r , int x , int lx , int rx) {
     int mid = (lx  + rx) / 2;

     if(mid >= l && mid <= r) {
        ll val1 = elem[1][x][mid - l];
        ll val2 = elem[2][x][r - mid];
        return Ask(val1 , val2);
     }

     else if(mid + 1 >= l && mid + 1 <= r) {
        ll val1 = elem[1][x][(mid + 1) - l];
        ll val2 = elem[2][x][r - (mid + 1)];
        return Ask(val1 , val2);
     }

     if(mid + 1 < l) return Get(l , r , 2 * x , lx , mid);
     else return Get(l , r , 2 * x + 1 , mid + 1 , rx);
}

void Init(int N, int A[]) {

    for(int i = 1 ; i <= N ; ++i) s[i] = A[i];

    Build(1 , 1 , M);
}

int Query(int L, int R) {

  cout << Get(L , R , 1 , 1 , size) << endl;

  return 0;
}

Compilation message

secret.cpp: In function 'void Build(int, int, int)':
secret.cpp:31:12: warning: unused variable 'res' [-Wunused-variable]
   31 |         ll res = Ask(s[i] , elem[2][x].back());
      |            ^~~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:31:25: warning: iteration 510 invokes undefined behavior [-Waggressive-loop-optimizations]
   31 |         ll res = Ask(s[i] , elem[2][x].back());
      |                      ~~~^
secret.cpp:30:30: note: within this loop
   30 |      for(int i = mid + 2 ; i <= rx ; ++i) {
      |                            ~~^~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20005 ms 2380 KB Time limit exceeded
2 Execution timed out 20056 ms 2444 KB Time limit exceeded
3 Execution timed out 20008 ms 2332 KB Time limit exceeded
4 Execution timed out 20042 ms 4344 KB Time limit exceeded
5 Execution timed out 20050 ms 4236 KB Time limit exceeded
6 Execution timed out 20073 ms 4336 KB Time limit exceeded
7 Execution timed out 20023 ms 4300 KB Time limit exceeded
8 Execution timed out 20031 ms 4324 KB Time limit exceeded
9 Execution timed out 20039 ms 4348 KB Time limit exceeded
10 Execution timed out 20029 ms 4292 KB Time limit exceeded