Submission #1015028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015028		8pete8	Fish 2 (JOI22_fish2)	C++17	25 / 100	4081 ms	3936 KiB

fish2

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
int val[mxn+10],put[mxn+10],pref[mxn+10];
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
void solve(int l,int r){
    stack<int>st,st2;
    int tmp=val[l-1];
    val[l-1]=inf;
    st.push(l-1);
    st2.push(l-1);
    pref[l-1]=put[l-1]=0;
    for(int i=l;i<=r;i++){
        pref[i]=val[i]+pref[i-1];
        put[i]=0;
        while(val[i]>val[st.top()])st.pop();
        if(pref[i-1]-pref[st.top()]<val[i])put[st.top()+1]++,put[i]--;
        while(val[i]>=val[st2.top()]){
            if(pref[i-1]-pref[st2.top()]<val[st2.top()])put[st2.top()+1]++,put[i]--;
            st2.pop();
        }
        st.push(i);
        st2.push(i);
    }
    while(!st2.empty()){
        if(st2.top()!=l-1&&pref[r]-pref[st2.top()]<val[st2.top()]){
            put[st2.top()+1]++;
        }
        st2.pop();
    }
    val[l-1]=tmp;
    int ans=0;
    for(int i=l;i<=r;i++){
        put[i]+=put[i-1],ans+=(!put[i]);
    }
    cout<<ans<<'\n';
}
int32_t main(){
    fastio
    //brute force check
    cin>>n;
    for(int i=1;i<=n;i++)cin>>val[i];
    int q;cin>>q;
    while(q--){
        int t,x,y;cin>>t>>x>>y;
        if(t==1)val[x]=y;
        else solve(x,y);
    }
}
/*
each element will be bounded by range l,r
where sum(l+1,r-1)<minval(l,r)
then every element in range l,r cant go out of range l,r

range where x is one of the bound  can be found 
by finding the first left and right pos y where val[y]>=val[x]
because if val[a]>=x and a<y
then range (a,y) will also cover if range (a,l) cover

we can update range and find y for the updated x by bin search+seg tree
how do we answer?
let ql,qr be the queried range
we have list of bounded range(l,r)
if l,r is in ql,qr or l,r intersect with ql,qr then we can still use that l,r
but if l,r cover ql,qr then we can use that l,r?
*/

Compilation message (stderr)

fish2.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
fish2.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void setIO(string name){
      |                       ^
fish2.cpp:44:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 | void solve(int l,int r){
      |                       ^
fish2.cpp:76:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   76 | int32_t main(){
      |              ^
fish2.cpp: In function 'void setIO(std::string)':
fish2.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17