// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
//#ifdef arwaeystoamneg
if (sz(s))
{
freopen((s + ".in").c_str(), "r", stdin);
if (s != "test1")
freopen((s + ".out").c_str(), "w", stdout);
}
//#endif
}
#ifndef arwaeystoamneg
#include "secret.h"
#endif
#ifdef arwaeystoamneg
#define MAX_N 1000
#define MAX_Q 10000
#define MAX_VALUE 1000000000
static int N;
static int A[MAX_N];
static int Q;
static int L[MAX_Q];
static int R[MAX_Q];
static int secret_count;
int Secret(int X, int Y) {
++secret_count;
if (!(0 <= X && X <= MAX_VALUE)) {
fprintf(stderr, "Wrong Answer [1]\n");
exit(0);
}
if (!(0 <= Y && Y <= MAX_VALUE)) {
fprintf(stderr, "Wrong Answer [1]\n");
exit(0);
}
return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
}
#endif
const int MAX = 1005, SZ = 11;
int n, a[MAX];
vi prefix[MAX], suffix[MAX];
void init(int tl, int tr)
{
if (tl == tr)return;
int m = (tl + tr) / 2;
assert(!sz(prefix[m + 1]) && !sz(suffix[m]));
prefix[m + 1].pb(a[m + 1]);
FOR(i, m + 2, tr + 1)
{
prefix[m + 1].pb(Secret(prefix[m + 1].back(), a[i]));
}
suffix[m].pb(a[m]);
ROF(i, tl, m)
{
suffix[m].pb(Secret(a[i], suffix[m].back()));
}
init(tl, m);
init(m + 1, tr);
}
int solve(int tl, int tr, int l, int r)
{
int m = (tl + tr) / 2;
if (m >= l && m < r)
{
return Secret(suffix[m][m - l], prefix[m + 1][r - (m + 1)]);
}
if (m >= r)return solve(tl, m, l, r);
else return solve(m + 1, tr, l, r);
}
void Init(int N, int A[])
{
n = N;
F0R(i, n)a[i] = A[i];
init(0, n - 1);
}
int Query(int L, int R)
{
if (L == R)
{
return a[L];
}
return solve(0, n - 1, L, R);
}
#ifdef arwaeystoamneg
int main()
{
setIO("test1");
int i, j;
int secret_count_by_init;
int max_secret_count_by_query = 0;
if (1 != scanf("%d", &N)) {
fprintf(stderr, "error: cannot read N.\n");
exit(1);
}
if (!(1 <= N && N <= MAX_N)) {
fprintf(stderr, "error: N is out of bounds.\n");
exit(1);
}
for (i = 0; i < N; ++i) {
if (1 != scanf("%d", &A[i])) {
fprintf(stderr, "error: cannot read A[%d].\n", i);
exit(1);
}
if (!(0 <= A[i] && A[i] <= MAX_VALUE)) {
fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
exit(1);
}
}
if (1 != scanf("%d", &Q)) {
fprintf(stderr, "error: cannot read Q.\n");
exit(1);
}
if (!(0 <= Q && Q <= MAX_Q)) {
fprintf(stderr, "error: Q is out of bounds.\n");
exit(1);
}
for (j = 0; j < Q; ++j) {
if (2 != scanf("%d%d", &L[j], &R[j])) {
fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
exit(1);
}
if (!(0 <= L[j] && L[j] <= R[j] && R[j] <= N - 1)) {
fprintf(stderr,
"error: L[%d] and R[%d] do not satisfy the constraints.\n",
j, j);
exit(1);
}
}
secret_count = 0;
Init(N, A);
secret_count_by_init = secret_count;
for (j = 0; j < Q; ++j) {
secret_count = 0;
printf("%d\n", Query(L[j], R[j]));
if (max_secret_count_by_query < secret_count) {
max_secret_count_by_query = secret_count;
}
}
fprintf(stderr, "number of calls to Secret by Init : %d\n",
secret_count_by_init);
fprintf(stderr, "maximum number of calls to Secret by Query : %d\n",
max_secret_count_by_query);
return 0;
}
#endif
Compilation message
secret.cpp: In function 'void setIO(std::string)':
secret.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
49 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
secret.cpp:51:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
51 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
2468 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
147 ms |
2432 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
144 ms |
2464 KB |
Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
553 ms |
4500 KB |
Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
540 ms |
4596 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
508 ms |
4476 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
527 ms |
4404 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
522 ms |
4484 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
511 ms |
4440 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
513 ms |
4548 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
