oj.uz

Submission #981791

# Submission time Handle Problem Language Result Execution time Memory
981791 2024-05-13T15:00:12 Z shadow_sami Fish 3 (JOI24_fish3) C++17
28 / 100
 369 ms 53076 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 3e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
ll a[mx];
ll pref[mx];
ll prv[mx];
ll na[mx];
stack<ll> sck;
vector<pi> lis[mx];

typedef struct SEGMENT_TREE{
	vi arr,laz;
	ll range;
	void init(ll k){
		range = 4 * k;
		arr.resize(range);
		laz.resize(range);
		fip(0,range){
			arr[i] = 0;
			laz[i] = -1;
		}
		return;
	}
	void prop(ll ptr,ll l,ll r){
		if(laz[ptr]!=-1){
			arr[ptr] = laz[ptr] * (r-l+1);			
			if(l!=r){
				laz[2*ptr] = laz[ptr];
				laz[2*ptr+1] = laz[ptr];
			}
		}
		laz[ptr] = -1;
		return;
	}
	void update(ll ptr,ll l,ll r,ll st,ll en, ll val){
		prop(ptr,l,r);
		if(l>en || r<st)
			return;
		if(l>=st && r<=en){
			laz[ptr] = val;
			prop(ptr,l,r);
			return;
		}
		ll mid = l + (r-l) / 2;
		update(2*ptr,l,mid,st,en,val);
		update(2*ptr+1,mid+1,r,st,en,val);
		arr[ptr] = arr[2*ptr] + arr[2*ptr+1];
		return;
	}
	ll query(ll ptr,ll l,ll r,ll st,ll en){
		prop(ptr,l,r);
		if(l>en || r<st)
			return 0;
		if(l>=st && r<=en)
			return arr[ptr];		
		ll mid = l + (r-l) / 2;				
		return query(2*ptr,l,mid,st,en)+query(2*ptr+1,mid+1,r,st,en);
	}
}SGT;

SGT sgt;

ll get(ll l,ll r){
	if(r<l)
		return 0;
	return pref[r] - (l?pref[l-1]:0);
}

void emptify(){
	while(sck.size())
		sck.pop();
	return;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>tp;
        fip(0,n)
        	cin>>a[i];
        fip(0,n)	
        	pref[i] = a[i] + (i?pref[i-1]:0ll);
        ll sr,de;
        cin>>m;
        sgt.init(n);
        emptify();
        fip(0,n){
        	while(sck.size() && a[sck.top()] > a[i])
        		sck.pop();
        	if(sck.size())
        		prv[i] = sck.top();
        	else
        		prv[i] = -1;
        	sck.push(i);
        }
        fip(0,m){
        	cin>>sr>>de;
        	sr--,de--;        
        	lis[de].push_back({sr,i});
        }
        fip(0,n){
        	tp = prv[i];
        	tp++;
        	sgt.update(1,0,n-1,tp,i,a[i]);
        	fx(lis[i]){
        		tp = x.ff;
        		ans = get(tp,i);        		
        		ans -= sgt.query(1,0,n-1,tp,i);        		
        		na[x.ss] = ans;
        	}        		        		
        }
        fip(0,m)
        	cout<<na[i]<<nli;        
        // cout<<log2(1e12)<<nli;

    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Incorrect 5 ms 14940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 48952 KB Output is correct
2 Correct 311 ms 49068 KB Output is correct
3 Incorrect 99 ms 25540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 29212 KB Output is correct
2 Correct 363 ms 52912 KB Output is correct
3 Correct 333 ms 53076 KB Output is correct
4 Correct 339 ms 52820 KB Output is correct
5 Correct 322 ms 52932 KB Output is correct
6 Correct 310 ms 48212 KB Output is correct
7 Correct 317 ms 48352 KB Output is correct
8 Correct 319 ms 50004 KB Output is correct
9 Correct 325 ms 49832 KB Output is correct
10 Correct 369 ms 50812 KB Output is correct
11 Correct 325 ms 50516 KB Output is correct
12 Correct 338 ms 52192 KB Output is correct
13 Correct 313 ms 52168 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 44132 KB Output is correct
2 Correct 313 ms 47964 KB Output is correct
3 Correct 201 ms 30844 KB Output is correct
4 Correct 336 ms 49532 KB Output is correct
5 Correct 321 ms 49868 KB Output is correct
6 Correct 339 ms 52580 KB Output is correct
7 Correct 295 ms 47448 KB Output is correct
8 Correct 345 ms 52616 KB Output is correct
9 Incorrect 307 ms 48040 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Incorrect 5 ms 14940 KB Output isn't correct
4 Halted 0 ms 0 KB -