Submission #942737

#TimeUsernameProblemLanguageResultExecution timeMemory
942737FoolestboySum Zero (RMI20_sumzero)C++14
0 / 100
8 ms31580 KiB
#include <bits/stdc++.h> #define SQR(x) (1LL * ((x) * (x))) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(s) (int)s.size() #define prev __prev #define next __next #define left __left #define right __right #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vll vector<ll> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef unsigned int ui; using namespace std; const int mod = 1e9 + 7; const int INF = 1e9 + 7; const ll INFLL = (ll)2e18 + 7LL; const ld PI = acos(-1); const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1}; const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1}; template<class BUI, class TRONG> bool minimize(BUI &x, const TRONG y){ if(x > y){ x = y; return true; } else return false; } template<class BUI, class TRONG> bool maximize(BUI &x, const TRONG y){ if(x < y){ x = y; return true; } else return false; } /* Author : Bui Nguyen Duc Trong, Luong Van Chanh High School for the gifted*/ /* Template is copied by Trong */ /** Losing in Provincial Contests **/ /** TRYING HARDER**/ /** ORZ **/ /* -----------------[ MAIN CODE GOES HERE ]----------------- */ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 4e5 + 10; const int LOG = 18; int n, q; int a[N]; vector<ll> val; int nxt[N][LOG + 1], z[N]; int Rand(int l, int r) { return l + rng() % (r - l + 1); } void solve(){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; ll cur = 0; for(int i = 1; i <= n; i++){ cur += a[i]; val.push_back(cur); } val.push_back(0); sort(all(val)); val.resize(unique(all(val)) - val.begin()); cur = 0; for(int i = 0; i <= n; i++) cur += a[i], a[i] = lower_bound(all(val), cur) - val.begin(); memset(nxt, 0x3f, sizeof nxt); for(int i = 0; i <= n + 1; i++) nxt[i][0] = z[i] = n + 1; for(int i = n; i >= 0; i--){ nxt[i][0] = min(nxt[i + 1][0], z[a[i]]); z[a[i]] = i; } for(int j = 1; j <= LOG; j++) for(int i = 0; i <= n; i++){ if(nxt[i][j - 1] <= n + 1) nxt[i][j] = nxt[nxt[i][j - 1]][j - 1]; } cin >> q; while(q--){ int l, r; cin >> l >> r; int ans = 0; int p = l - 1; for(int i = LOG; i >= 0; i--){ if(nxt[p][i] <= r){ ans += MASK(i); p = nxt[p][i]; } } cout << ans << '\n'; } } /* 10 1 2 -3 0 1 -4 3 2 -1 1 3 1 10 1 5 2 9 */ signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); const bool multitest = 0; int tt = 1; if(multitest) cin >> tt; while( tt-- ){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...