제출 #1338435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338435		vjudge1	Sum Zero (RMI20_sumzero)	C++20	100 / 100	321 ms	21244 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 4e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = 1e9;
const ll INF = LLONG_MAX;

const int LG = 8;
int n, q, a[N], st[LG + 1][N];
ll pfs[N];

bool comp(int i, int j){
    if(pfs[i] == pfs[j]) return i < j;
    return pfs[i] < pfs[j];
}

void solve(){

    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i], pfs[i] = pfs[i - 1] + a[i];
    iota(a, a + n + 1, 0);
    sort(a, a + n + 1, comp);

    // for(int i = 0; i <= n; i++) cout<<pfs[i]<<" "; cout<<'\n';
    // for(int i = 0; i <= n; i++) cout<<a[i]<<" "; cout<<'\n';
    // for(int i = 0; i <= n; i++) cout<<pfs[a[i]]<<" "; cout<<'\n';
    
    for(int i = n; i >= 0; i--){
        int j = a[i];
        if(i == n || pfs[j] != pfs[a[i + 1]]) st[0][j + 1] = n + 2;
        else st[0][j + 1] = a[i + 1] + 1;
    }
    for(int i = n - 1; i >= 1; i--) st[0][i] = min(st[0][i], st[0][i + 1]);
    // for(int i = 1; i <= n; i++) cout<<st[0][i]<<" "; cout<<'\n';
    for(int j = 0; j <= LG; j++) st[j][n + 1] = st[j][n + 2] = n + 2;
    for(int j = 1; j <= LG; j++){
        for(int i = 1; i <= n; i++){
            if(st[j - 1][st[j - 1][st[j - 1][st[j - 1][st[j - 1][i]]]]] > n + 1) st[j][i] = n + 2;
            else st[j][i] = st[j - 1][st[j - 1][st[j - 1][st[j - 1][st[j - 1][i]]]]];
        }
        // cout<<"------- "<<j<<'\n';
        // for(int i = 1; i <= n; i++) cout<<st[j][i]<<" "; cout<<'\n';
    }
    // cout<<"ok"; return;
    cin>>q;
    while(q--){
        int l, r; cin>>l>>r; r++;
        int pw = 390625, ans = 0;
        for(int j = LG; j >= 0; j--){
            if(st[j][l] <= r) l = st[j][l], ans += pw;
            if(st[j][l] <= r) l = st[j][l], ans += pw;
            if(st[j][l] <= r) l = st[j][l], ans += pw;
            if(st[j][l] <= r) l = st[j][l], ans += pw;
            // cout<<"### "<<j<<" "<<l<<" "<<ans<<" "<<pw<<'\n';
            pw /= 5;
        }
        cout<<ans<<'\n';
    }
}

signed main(){
    
    if(fopen("input.txt", "r")){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    else if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin>>tc;
    while(tc--) solve();
}

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'int main()':
sumzero.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sumzero.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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