Submission #1272350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272350		abyfu	Sum Zero (RMI20_sumzero)	C++20	0 / 100	1095 ms	712 KiB

sumzero

//OwO
//#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define namein "input.txt"
#define nameout "output.txt"
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define m_pi acos(-1)
using namespace std;
const ll inf = 7e18;    
const int linf = 1e8;

void file(){
    if (fopen(namein, "r")){
        freopen(namein, "r", stdin);
        freopen(nameout, "w", stdout);
    }   
}

const ll mod = 998244353;
const int N = 4e5 + 5, M = 5e5 + 5;
int n, a[N];//, p[N];
int dp[N];

void run(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        
        //p[i] = p[i - 1] + a[i];
    }
    int q; cin >> q;
    while (q--){
        int l, r; cin >> l >> r;
        if (n <= 5000){
            map<ll, int> sx;
            map<ll, int> pos;
            dp[l - 1] = 0;
            sx[0] = 0;
            pos[0] = l - 1;
            ll sum = 0;
            //dp[l - 1] = 0;
            for (int i = l; i <= r; i++){
                sum += a[i];
                dp[i] = 0;
                if (sx[sum] != 0 || sum == 0){
                    dp[i] = dp[pos[sum]] + 1;
                }
                dp[i] = max(dp[i - 1], dp[i]);
                if (sx[sum] <= dp[i]){
                    pos[sum] = i;
                    sx[sum] = dp[i];
                }
                //cout << sum << " " << dp[i] << " " << sx[sum] << " " << pos[sum] << "\n";
            }
            //cout << "\n";
            cout << dp[r] << "\n";
        }
    }
}   

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    file();
    run();
}

Compilation message (stderr)

sumzero.cpp: In function 'void file()':
sumzero.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(namein, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sumzero.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(nameout, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39