제출 #243242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243242		tranxuanbach	비밀 (JOI14_secret)	C++17	100 / 100	526 ms	5052 KiB

secret

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "secret.h"
using namespace std;
using namespace __gnu_pbds;

// Optimization

//#pragma GCC optimize("O3")
#define endl '\n'

// Shortcut

// #define int long long
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define Ford(i, r, l) for (int i = r; i > l; i--)
#define FordE(i, r, l) for (int i = r; i >= l; i--)
#define Fora(i, a) for (auto i : a)

// I/O & Debug

#define PrintV(a) Fora(iiii, a) cout << iiii << ' '; cout << endl;
#define PrintVl(a) Fora(iiii, a) cout << iiii << endl;
#define PrintA(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << ' '; cout << endl;
#define PrintAl(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << endl;
#define Ptest(x) return cout << x, 0;
#define gl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
/*
#define debug(args...){ string _sDEB = #args; replace(_sDEB.begin(), _sDEB.end(), ',', ' '); stringstream _ssDEB(_sDEB); istream_iterator<string> _itDEB(_ssDEB); DEB(_itDEB, args); }
void DEB(istream_iterator<string> it) {}
template<typename T, typename... Args>
void DEB(istream_iterator<string> it, T a, Args... args){
    cout << *it << " = " << a << endl;
    DEB(++it, args...);
}
*/

// Functions

//#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define bend(a) a.begin(), a.end()
#define rbend(a) a.rbegin(), a.rend()
#define mset(a) memset(a, 0, sizeof(a))
#define mset1(a) memset(a, 1, sizeof(a))
#define msetn1(a) memset(a, -1, sizeof(a))
#define msetinf(a) memset(a, 0x3f, sizeof(a))
#define gcd __gcd
#define __builtin_popcount __builtin_popcountll
//mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
//int randt(int l, int r){ return (rando() % (r - l + 1) + l); }

// Data Structure

#define pque priority_queue
#define mts multiset
#define y0 _y0_
#define y1 _y1_
#define div divi
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;

const int N = 1e3, PWN = 1024, LV = 11;
int mod = 1e9 + 7, mod1 = 998244353, mod2 = 1e9 + 9, inf = 1e9;
ll infll = 1e18 + 7;

//int Secret(int X, int Y);

int b[N];
int table[LV][PWN];
int maxlev, sz;
map <pair <int, int>, int> mpp;

void build(int lev = 0, int l = 0, int r = sz){
    int m = (l + r - 1) >> 1;
    table[lev][m] = b[m];
    FordE(i, m - 1, l){
        if (mpp.find({i, m}) == mpp.end()){
            table[lev][i] = Secret(b[i], table[lev][i + 1]);
            mpp[{i, m}] = table[lev][i];
        }
        else{
            table[lev][i] = mpp[{i, m}];
        }
    }
    if (m + 1 < r){
        table[lev][m + 1] = b[m + 1];
        For(i, m + 2, r){
            if (mpp.find({m + 1, i}) == mpp.end()){
                table[lev][i] = Secret(table[lev][i - 1], b[i]);
                mpp[{m + 1, i}] = table[lev][i];
            }
            else{
                table[lev][i] = mpp[{m + 1, i}];
            }
        }
    }
    if (l + 1 != r){
        build(lev + 1, l, m + 1);
        build(lev + 1, m + 1, r);
    }
}

void Init(int n, int a[]){
	For(i, 0, n){
		b[i] = a[i];
	}
    sz = n;
    maxlev = __builtin_clz(n) ^ 31;
    if ((1 << maxlev) != n){
        sz = 1 << ++maxlev;
    }
    build();
//    For(lev, 0, maxlev){
//    	For(i, 0, n){
//    		cout << lev << ' ' << i << ' ' << table[lev][i] << endl;
//		}
//	}
}

int Query(int l, int r){
	if (l == r){
		return b[l];
	}
	int k2 = __builtin_clz(l ^ r) ^ 31;
	int lev = maxlev - 1 - k2;
	int m = ((r >> k2) << k2) - 1;
//	cout << "Q " << l << ' ' << r << ' ' << k2 << ' ' << lev << endl;
	int ans = table[lev][l];
	if (r > m){
		ans = Secret(ans, table[lev][r]);
	}
	return ans;
}

// DEBUGGING SECTION ======================================================================================================

//int n, q;
//int a[N];
//
//int Secret(int X, int Y){
//	return (X + 2 * (Y / 2) < inf) ? (X + 2 * (Y / 2)) : inf;
//}
//
//signed main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0); cout.tie(0);
//	cin >> n;
//	For(i, 0, n){
//		cin >> a[i];
//	}
//	Init(n, a);
//	cin >> q;
//	while (q--){
//		int l, r; cin >> l >> r; cout << Query(l, r) << endl;
//	}
//}

/*
==================================+
INPUT:                            |
------------------------------    |
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/

• Subtask 1: 100 / 100