Submission #394953

#	Time	Username	Problem	Language	Result	Execution time	Memory
394953		arwaeystoamneg	Secret (JOI14_secret)	C++17	100 / 100	553 ms	4596 KiB

secret

// 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 (stderr)

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);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100