답안 #735287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735287 2023-05-03T20:21:15 Z Wael 비밀 (JOI14_secret) C++14
0 / 100
477 ms 9776 KB
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int long long
#define F first
#define S second
//#define endl '\n'
#define INT INT_MAX
int const M = 1e3 + 30 , N = 3e6 , lg = 25 , mod = 1e9 + 7;
int dx[] = {0 , 0 , -1 , 1 , 1 , 1 , -1 , -1};
int dy[] = {1 , -1 , 0 , 0 , 1 , -1 , 1 , -1};
int T , n , j , a[M] , Q , l , r , Size = 1024 , s[M];
long long ans[M][M];

/*
inline ll Secret(int x , int y) {
    //cout << x << " " << y << endl;
    int res;
    res = x + y;
    return res;
}
*/

void Go(int x = 1 , int lx = 1 , int rx = Size) {

    if(lx == rx) {
        ans[lx][rx] = s[lx];
        return;
    }
    int mid = (lx + rx) / 2;
    int a = mid , b = mid + 1;
    ans[b][b] = s[b];
    for(int i = b + 1 ; i <= rx ; ++i) ans[b][i] = Secret(ans[b][i - 1] , s[i]);

    ans[a][a] = s[a];
    for(int i = a - 1 ; i >= lx ; --i) ans[i][a] = Secret(ans[i + 1][a] , s[i]);
    Go(2 * x , lx , mid);
    Go(2 * x + 1 , mid + 1 , rx);

}

int Get(int l , int r , int x = 1 , int lx = 1 , int rx = Size) {

    int mid = (lx + rx) / 2;
    if((mid >= l && mid <= r)) {
        int res = 0;
        if(mid >= l && mid + 1 <= r) res = Secret(ans[l][mid] , ans[mid + 1][r]);
        else if(mid == r) res = ans[l][mid];
        return res;
    }
    if(l > mid) return Get(l , r , 2 * x + 1 , mid + 1 , rx);
    else return Get(l , r , 2 * x,  lx , mid);

}

void Init(int sz , int ar[]) {

    n = sz;
    for(int i = 1 ; i <= n ; ++i) s[i] = ar[i - 1];
    Go();

}

int Query(int l , int r) {
    ++l , ++r;
    if(l == r) return s[l];
    return Get(l , r);
}

# 결과 실행 시간 메모리 Grader output
1 Incorrect 132 ms 7920 KB Wrong Answer: Query(113, 206) - expected : 536899947, actual : 538256673.
2 Incorrect 118 ms 7884 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 122 ms 7888 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 162768982.
4 Incorrect 451 ms 9772 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 546373765.
5 Incorrect 436 ms 9712 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 707448136.
6 Incorrect 436 ms 9724 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 722663411.
7 Incorrect 447 ms 9776 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 54559803.
8 Incorrect 477 ms 9740 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 822146056.
9 Incorrect 472 ms 9776 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 408296780.
10 Incorrect 434 ms 9708 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 67347979.