oj.uz

Submission #639697

# Submission time Handle Problem Language Result Execution time Memory
639697 2022-09-11T06:47:03 Z maomao90 Sum Zero (RMI20_sumzero) C++17
61 / 100
 81 ms 13392 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
 
#ifndef DEBUG
#define cerr if (0) cerr
#endif
 
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 100005;

int n, q;
int c[MAXN];
int lr[MAXN];
map<ll, int> lst;
vii rgs, orgs;
int p[MAXN];
vi adj[MAXN];
int ans[MAXN];

vi ask[MAXN];
bool vis[MAXN];
vi stk;
void dfs(int u) {
    stk.pb(u);
    cerr << u << ": " << rgs[u].FI << ' ' << rgs[u].SE << '\n';
    for (int i : ask[u]) {
	cerr << ' ' << i << '\n';
	int lo = 0, hi = SZ(stk) - 1;
	while (lo < hi) {
	    int mid = lo + hi >> 1;
	    if (rgs[stk[mid]].SE <= lr[i]) {
		hi = mid;
	    } else {
		lo = mid + 1;
	    }
	}
	cerr << "  " << lo << '\n';
	ans[i] = SZ(stk) - lo - 1 + (rgs[stk[lo]].SE <= lr[i]);
    }
    for (int v : adj[u]) {
	vis[v] = 1;
	dfs(v);
    }
    stk.pop_back();
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    REP (i, 1, n + 1) {
	cin >> c[i];
    }
    ll sm = 0;
    REP (i, 0, n + 1) {
	sm += c[i];
	if (lst.find(sm) != lst.end()) {
	    rgs.pb({lst[sm], i});
	}
	lst[sm] = i;
    }
    lst.clear();
    cin >> q;
    REP (i, 1, q + 1) {
	int l; cin >> l >> lr[i];
	l--;
	orgs.pb({-i, l});
    }
    sort(ALL(rgs), [&] (ii l, ii r) {
	    return l.SE < r.SE;
	    });
    sort(ALL(orgs), [&] (ii l, ii r) {
	    return l.SE < r.SE;
	    });
    int ptr = 0;
    memset(p, -1, sizeof p);
    REP (i, 0, SZ(rgs)) {
	while (ptr < i && rgs[ptr].SE <= rgs[i].FI) {
	    p[ptr] = i;
	    ptr++;
	}
    }
    int optr = 0;
    REP (i, 0, SZ(rgs)) {
	while (optr < SZ(orgs) && orgs[optr].SE <= rgs[i].FI) {
	    ask[i].pb(-orgs[optr].FI);
	    optr++;
	}
    }
    orgs.clear();
    REP (i, 0, SZ(rgs)) {
	adj[p[i]].pb(i);
    }
    RREP (i, SZ(rgs) - 1, 0) {
	if (vis[i]) {
	    continue;
	}
	vis[i] = 1;
	dfs(i);
    }
    REP (i, 1, q + 1) {
	cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

sumzero.cpp: In function 'void dfs(int)':
sumzero.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |      int mid = lo + hi >> 1;
      |                ~~~^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5716 KB Output is correct
2 Correct 6 ms 5696 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5716 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5716 KB Output is correct
2 Correct 6 ms 5696 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5716 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct
7 Correct 78 ms 13192 KB Output is correct
8 Correct 78 ms 13296 KB Output is correct
9 Correct 80 ms 12716 KB Output is correct
10 Correct 81 ms 13252 KB Output is correct
11 Correct 73 ms 13392 KB Output is correct
12 Correct 80 ms 12636 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5716 KB Output is correct
2 Correct 6 ms 5696 KB Output is correct
3 Correct 6 ms 5844 KB Output is correct
4 Correct 6 ms 5716 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 6 ms 5844 KB Output is correct
7 Correct 78 ms 13192 KB Output is correct
8 Correct 78 ms 13296 KB Output is correct
9 Correct 80 ms 12716 KB Output is correct
10 Correct 81 ms 13252 KB Output is correct
11 Correct 73 ms 13392 KB Output is correct
12 Correct 80 ms 12636 KB Output is correct
13 Incorrect 9 ms 6312 KB Output isn't correct
14 Halted 0 ms 0 KB -