Submission #1337808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337808		kokokai	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	0 / 100	4091 ms	4132 KiB

mizuyokan2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define task "text"
#define fi first
#define se second
const int N = 255555;
ll L[N];
int nxt[N];
int sufmin[N];
int n,q;
namespace subtask3{
    bool check(){
        return q <= 10;
    }
    int takeans(int p,int r){
        int ans=0;
        while(sufmin[p] <= r){
            ans += 2;
            p=sufmin[p];
        }
        ll sum=0;
        for(int i=p+1;i<=r;i++) sum += L[i];
        if(L[p] < sum) ans++;
        return ans;
    }
    void solve(){
        while(q--){
            int x,y,a,b;
            cin>>x>>y>>a>>b;
            L[x]=y;
            for(int i=n;i>=1;i--){
                int np=-1;
                ll sum=0;
                for(int j=i+1;j<min(n,i+60);j++){
                    sum += L[j];
                    if(L[i] < sum && sum > L[j+1]){
                        np=j+1;
                        break;
                    }
                }
                nxt[i]=np;
                if(np == -1) nxt[i]=1e9;
            }
            sufmin[n+1]=1e9;
            for(int i=n;i>=1;i--){
                sufmin[i]=min(nxt[i],sufmin[i+1]);
            }

            int r=b;
            a++;
            int ans=1;
            if(nxt[a] <= r){
                ans=max(ans,3+takeans(nxt[a],r));
            }else{
                ll sum=0;
                for(int i=a+1;i<=b;i++) sum+=L[i];
                if(L[a] < sum) ans=max(ans,2);
            }
            int p=a;
            ll sum=0;
            for(int i=a;i<b;i++){
                sum += L[i];
                if(sum > L[i+1]){
                    p=i+1;
                    break;
                }
            }
                        //cerr<<x<<' '<<y<<'\n';

            if(p>a){
                ans=max(ans,2+takeans(p,r));
            }
            cout<<ans<<'\n';
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for(int i=1;i<=n;i++) cin>>L[i];
    cin>>q;
    subtask3::solve();


}

Compilation message (stderr)

mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11