oj.uz

Submission #977789

# Submission time Handle Problem Language Result Execution time Memory
977789 2024-05-08T11:07:46 Z NoLove Secret (JOI14_secret) C++14
100 / 100
 395 ms 4516 KB 
#include "secret.h"
/**
 *    author : Lăng Trọng Đạt
 *    created: 08-05-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
// #define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;


const int MAXN = 1e3 + 5;
int g[MAXN];
int n;

int mask[MAXN];
int dat[12][MAXN];
void build(int l, int r, int lv) {
	if (l != r) {
		int m = (l + r) / 2;
		dat[lv][m] = g[m];
		for (int i = m - 1; i >= l; i--) {
			dat[lv][i] = Secret(g[i], dat[lv][i + 1]);
		}
		dat[lv][m + 1] = g[m + 1];
		mask[m + 1] ^= 1 << lv;
		for (int i = m + 2; i <= r; i++) {
			dat[lv][i] = Secret(dat[lv][i - 1], g[i]);
			mask[i] ^= 1 << lv;
		}

		build(l, m, lv + 1);
		build(m + 1, r, lv + 1);
	}
}
void Init(int N, int A[]) {
    n = N;
	FOR(i, 0, n - 1) g[i] = A[i];
	build(0, n - 1, 0);
}

int Query(int L, int R) {
	if (L == R) return g[L];
	else {
		int bit = __builtin_ctz(mask[L] ^ mask[R]);
		return Secret(dat[bit][L], dat[bit][R]);
	}
  return 0;
}

Compilation message

secret.cpp:23:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int INF = 1e18;
      |                 ^~~~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:19:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   19 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
secret.cpp:53:2: note: in expansion of macro 'FOR'
   53 |  FOR(i, 0, n - 1) g[i] = A[i];
      |  ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2908 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 108 ms 2648 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 109 ms 2812 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 388 ms 4360 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 381 ms 4492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 385 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 395 ms 4356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 387 ms 4368 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 380 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 390 ms 4516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1