Submission #96052

#TimeUsernameProblemLanguageResultExecution timeMemory
96052bogdan10bosSecret (JOI14_secret)C++14
100 / 100
620 ms6024 KiB
#include <bits/stdc++.h> //#define DEBUG #ifndef DEBUG #include "secret.h" #endif #ifdef DEBUG int Secret(int, int); #endif using namespace std; namespace My { int N, I; int v[1005]; int id[1005][1005]; vector<int> lft[10005], rgt[10005]; void divide(int st, int dr) { if(st >= dr) return; id[st][dr] = ++I; int mij = st + (dr - st) / 2; int val = v[mij]; lft[I].push_back(val); for(int i = mij - 1; i >= st; i--) { val = Secret(v[i], val); lft[I].push_back(val); } val = v[mij + 1]; rgt[I].push_back(val); for(int i = mij + 2; i <= dr; i++) { val = Secret(val, v[i]); rgt[I].push_back(val); } divide(st, mij - 1); divide(mij + 2, dr); } void init(int _N, int A[]) { N = _N; I = 0; for(int i = 1; i <= N; i++) v[i] = A[i - 1]; divide(1, N); } int query(int st, int dr, int sti, int dri) { int mij = st + (dr - st) / 2; int I = id[st][dr]; if(sti == mij + 1) return rgt[I][dri - sti]; if(dri == mij) return lft[I][dri - sti]; if(sti <= mij && mij + 1 <= dri) return Secret(lft[I][mij - sti], rgt[I][dri - mij - 1]); if(dri < mij) return query(st, mij - 1, sti, dri); if(sti > mij + 1) return query(mij + 2, dr, sti, dri); return -1; } int query(int st, int dr) { st++; dr++; if(st == dr) return v[st]; return query(1, N, st, dr); } } void Init(int N, int A[]) { My::init(N, A); } int Query(int L, int R) { return My::query(L, R); } #ifdef DEBUG namespace Grader { #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; } int main() { 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; } } int Secret(int x, int y) { return Grader::Secret(x, y); } int main() { freopen("1.in", "r", stdin); Grader::main(); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...