oj.uz

Submission #201867

# Submission time Handle Problem Language Result Execution time Memory
201867 2020-02-12T12:13:01 Z zscoder Fire (JOI20_ho_t5) C++17
100 / 100
 549 ms 46328 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 200011;

struct Fenwick
{
	vector<ll> t;
    Fenwick(int n)
    {
        t.assign(n+1,0);
    }
    void reset(int n)
    {
		t.assign(n+1, 0);
	}
    void update(int p, ll v)
    {
        for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;
    }
    ll query(int r) //finds [1, r] sum
    {                     
        ll sum = 0;
        for (; r; r -= (r&(-r))) sum += t[r];
        return sum;
    }
    ll query(int l, int r) //finds [l, r] sum
    {
		if(l == 0) return query(r);
		return query(r) - query(l-1);
	}
};

vector<ii> queries[N+11];
ll ans[N+11];
ll a[N+11];
int par[N+11];
const int C = N+4;
Fenwick F(2*N+11),F2(2*N+11),Fsum(2*N+11),F2sum(2*N+11);
Fenwick F3(2*N+11),F3sum(2*N+11);
ll shift=-C;
int subsiz[N+11];
vi adj[N+11];
ll summax;

void addval(int x, ll val)
{
	F2.update(x-shift,val);
	F2sum.update(x-shift,val*(x-shift));
}

int calcsiz(int u)
{
	subsiz[u]=1;
	for(int v:adj[u])
	{
		subsiz[u]+=subsiz[v];
	}
	return subsiz[u];
}

void quit(int id)
{
	ll subsz = calcsiz(id);
	if(par[id]!=-1)
	{
		subsz+=(id-par[id]-1);
		ll val = a[par[id]]-a[id];
		F2.update(subsz-shift,-val);
		F2sum.update(subsz-shift,-val*1LL*(subsz-shift));
		F.update(subsz+C,val);
		Fsum.update(subsz+C,val*subsz);
	}
	//if(par[id]!=-1) subsz--;
}

ll query(int t)
{
	ll sum1 = Fsum.query(1,t+C)+ll(t)*F.query(t+C+1,2*N+10);
	ll sum2 = F2sum.query(1,t-shift)+ll(shift)*F2.query(1,t-shift)+ll(t)*F2.query(t-shift+1,2*N+10);
	sum2+=F3sum.query(t+1+C,2*N+10)-F3.query(t+1+C,2*N+10)*ll(t);
	return sum1+sum2+summax;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q; cin>>n>>q;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<q;i++)
	{
		int t,l,r; cin>>t>>l>>r;
		l--; r--;
		queries[r].pb({i,t});
		if(l>0) queries[l-1].pb({i,-t});
	}	
	memset(par,-1,sizeof(par));
	for(int i=0;i<n;i++)
	{
		//add the value
		summax+=a[i];
		if(i==0)
		{
			//addval(0,a[0]); 
			//summax+=a[0];
		}
		else
		{
			int cur=i-1;
			while(cur>=0&&a[i]>=a[cur])
			{
				quit(cur);
				cur=par[cur];
			}
			shift++;
			par[i]=cur;
			//int val = 0; 
			//if root then initial value = 1
			if(par[i]!=-1) 
			{
				summax-=(a[par[i]]-a[i])*1LL*(i-par[i]-1);
				F3.update(i-par[i]-1+C,a[par[i]]-a[i]);
				F3sum.update(i-par[i]-1+C,(i-par[i]-1)*1LL*(a[par[i]]-a[i]));
				//cerr<<"ADD VAL (NODE = "<<i<<") : "<<1+i-par[i]-1<<'\n';
				addval(1+i-par[i]-1,a[par[i]]-a[i]);
				adj[par[i]].pb(i);
			}
			//else summax+=a[i];
		}
		//solve the queries
		for(ii x:queries[i])
		{
			ll tmp = query(abs(x.se));
			ll sum=0;
			for(int j=0;j<=i;j++)
			{
				ll mx=0;
				for(int k=j;k>=max(0,j-(abs(x.se)));k--)
				{
					mx=max(mx,a[k]);
				}
				sum+=mx;
			}
			//cerr<<"QUERY TILL "<<i<<" WITH T = "<<abs(x.se)<<": "<<tmp<<' '<<sum<<'\n';
			if(x.se<0)
			{
				ans[x.fi]-=tmp;
			}
			else
			{
				ans[x.fi]+=tmp;
			}
		}
	}
	for(int i=0;i<q;i++)
	{
		cout<<ans[i]<<'\n';
	}
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29304 KB Output is correct
2 Correct 21 ms 29304 KB Output is correct
3 Correct 22 ms 29432 KB Output is correct
4 Correct 21 ms 29432 KB Output is correct
5 Correct 21 ms 29304 KB Output is correct
6 Correct 22 ms 29304 KB Output is correct
7 Correct 20 ms 29304 KB Output is correct
8 Correct 20 ms 29304 KB Output is correct
9 Correct 21 ms 29436 KB Output is correct
10 Correct 21 ms 29432 KB Output is correct
11 Correct 21 ms 29304 KB Output is correct
12 Correct 21 ms 29432 KB Output is correct
13 Correct 23 ms 29304 KB Output is correct
14 Correct 23 ms 29304 KB Output is correct
15 Correct 21 ms 29304 KB Output is correct
16 Correct 21 ms 29304 KB Output is correct
17 Correct 21 ms 29308 KB Output is correct
18 Correct 21 ms 29432 KB Output is correct
19 Correct 21 ms 29304 KB Output is correct
20 Correct 21 ms 29432 KB Output is correct
21 Correct 20 ms 29432 KB Output is correct
22 Correct 21 ms 29432 KB Output is correct
23 Correct 20 ms 29308 KB Output is correct
24 Correct 21 ms 29304 KB Output is correct
25 Correct 20 ms 29304 KB Output is correct
26 Correct 21 ms 29304 KB Output is correct
27 Correct 20 ms 29304 KB Output is correct
28 Correct 20 ms 29432 KB Output is correct
29 Correct 20 ms 29304 KB Output is correct
30 Correct 20 ms 29304 KB Output is correct
31 Correct 21 ms 29304 KB Output is correct
32 Correct 21 ms 29304 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29304 KB Output is correct
2 Correct 398 ms 45688 KB Output is correct
3 Correct 397 ms 45688 KB Output is correct
4 Correct 401 ms 45944 KB Output is correct
5 Correct 387 ms 45816 KB Output is correct
6 Correct 360 ms 45688 KB Output is correct
7 Correct 367 ms 45944 KB Output is correct
8 Correct 417 ms 45944 KB Output is correct
9 Correct 370 ms 45968 KB Output is correct
10 Correct 371 ms 45560 KB Output is correct
11 Correct 376 ms 46072 KB Output is correct
12 Correct 380 ms 45436 KB Output is correct
13 Correct 377 ms 45688 KB Output is correct
14 Correct 378 ms 45692 KB Output is correct
15 Correct 361 ms 45688 KB Output is correct
16 Correct 382 ms 45816 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29304 KB Output is correct
2 Correct 460 ms 45220 KB Output is correct
3 Correct 478 ms 44792 KB Output is correct
4 Correct 472 ms 45304 KB Output is correct
5 Correct 496 ms 44896 KB Output is correct
6 Correct 490 ms 44920 KB Output is correct
7 Correct 475 ms 45048 KB Output is correct
8 Correct 472 ms 45048 KB Output is correct
9 Correct 485 ms 44792 KB Output is correct
10 Correct 469 ms 44536 KB Output is correct
11 Correct 493 ms 45304 KB Output is correct
12 Correct 460 ms 44792 KB Output is correct
13 Correct 502 ms 45304 KB Output is correct
14 Correct 472 ms 44920 KB Output is correct
15 Correct 481 ms 45020 KB Output is correct
16 Correct 495 ms 44792 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 42488 KB Output is correct
2 Correct 485 ms 42488 KB Output is correct
3 Correct 457 ms 42744 KB Output is correct
4 Correct 481 ms 42440 KB Output is correct
5 Correct 484 ms 42488 KB Output is correct
6 Correct 473 ms 42360 KB Output is correct
7 Correct 465 ms 42616 KB Output is correct
8 Correct 451 ms 42488 KB Output is correct
9 Correct 480 ms 42616 KB Output is correct
10 Correct 455 ms 42616 KB Output is correct
11 Correct 458 ms 42616 KB Output is correct
12 Correct 498 ms 42708 KB Output is correct
13 Correct 454 ms 42620 KB Output is correct
14 Correct 480 ms 42488 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29304 KB Output is correct
2 Correct 21 ms 29304 KB Output is correct
3 Correct 22 ms 29432 KB Output is correct
4 Correct 21 ms 29432 KB Output is correct
5 Correct 21 ms 29304 KB Output is correct
6 Correct 22 ms 29304 KB Output is correct
7 Correct 20 ms 29304 KB Output is correct
8 Correct 20 ms 29304 KB Output is correct
9 Correct 21 ms 29436 KB Output is correct
10 Correct 21 ms 29432 KB Output is correct
11 Correct 21 ms 29304 KB Output is correct
12 Correct 21 ms 29432 KB Output is correct
13 Correct 23 ms 29304 KB Output is correct
14 Correct 23 ms 29304 KB Output is correct
15 Correct 21 ms 29304 KB Output is correct
16 Correct 21 ms 29304 KB Output is correct
17 Correct 21 ms 29308 KB Output is correct
18 Correct 21 ms 29432 KB Output is correct
19 Correct 21 ms 29304 KB Output is correct
20 Correct 21 ms 29432 KB Output is correct
21 Correct 20 ms 29432 KB Output is correct
22 Correct 21 ms 29432 KB Output is correct
23 Correct 20 ms 29308 KB Output is correct
24 Correct 21 ms 29304 KB Output is correct
25 Correct 20 ms 29304 KB Output is correct
26 Correct 21 ms 29304 KB Output is correct
27 Correct 20 ms 29304 KB Output is correct
28 Correct 20 ms 29432 KB Output is correct
29 Correct 20 ms 29304 KB Output is correct
30 Correct 20 ms 29304 KB Output is correct
31 Correct 21 ms 29304 KB Output is correct
32 Correct 21 ms 29304 KB Output is correct
33 Correct 530 ms 45876 KB Output is correct
34 Correct 549 ms 46328 KB Output is correct
35 Correct 542 ms 46100 KB Output is correct
36 Correct 536 ms 45688 KB Output is correct
37 Correct 525 ms 45688 KB Output is correct
38 Correct 535 ms 45872 KB Output is correct
39 Correct 501 ms 45688 KB Output is correct
40 Correct 505 ms 45692 KB Output is correct
41 Correct 502 ms 45688 KB Output is correct
42 Correct 530 ms 45972 KB Output is correct
43 Correct 426 ms 46200 KB Output is correct
44 Correct 408 ms 45816 KB Output is correct
45 Correct 420 ms 45792 KB Output is correct
46 Correct 415 ms 45692 KB Output is correct
47 Correct 407 ms 45560 KB Output is correct
48 Correct 411 ms 45560 KB Output is correct
49 Correct 408 ms 45560 KB Output is correct
50 Correct 423 ms 46036 KB Output is correct
51 Correct 457 ms 45992 KB Output is correct
52 Correct 421 ms 45776 KB Output is correct
53 Correct 429 ms 45704 KB Output is correct
54 Correct 390 ms 45560 KB Output is correct
55 Correct 395 ms 45560 KB Output is correct
56 Correct 409 ms 45944 KB Output is correct
57 Correct 397 ms 45560 KB Output is correct
58 Correct 402 ms 45944 KB Output is correct
59 Correct 398 ms 45688 KB Output is correct
60 Correct 397 ms 45688 KB Output is correct
61 Correct 401 ms 45944 KB Output is correct
62 Correct 387 ms 45816 KB Output is correct
63 Correct 360 ms 45688 KB Output is correct
64 Correct 367 ms 45944 KB Output is correct
65 Correct 417 ms 45944 KB Output is correct
66 Correct 370 ms 45968 KB Output is correct
67 Correct 371 ms 45560 KB Output is correct
68 Correct 376 ms 46072 KB Output is correct
69 Correct 380 ms 45436 KB Output is correct
70 Correct 377 ms 45688 KB Output is correct
71 Correct 378 ms 45692 KB Output is correct
72 Correct 361 ms 45688 KB Output is correct
73 Correct 382 ms 45816 KB Output is correct
74 Correct 460 ms 45220 KB Output is correct
75 Correct 478 ms 44792 KB Output is correct
76 Correct 472 ms 45304 KB Output is correct
77 Correct 496 ms 44896 KB Output is correct
78 Correct 490 ms 44920 KB Output is correct
79 Correct 475 ms 45048 KB Output is correct
80 Correct 472 ms 45048 KB Output is correct
81 Correct 485 ms 44792 KB Output is correct
82 Correct 469 ms 44536 KB Output is correct
83 Correct 493 ms 45304 KB Output is correct
84 Correct 460 ms 44792 KB Output is correct
85 Correct 502 ms 45304 KB Output is correct
86 Correct 472 ms 44920 KB Output is correct
87 Correct 481 ms 45020 KB Output is correct
88 Correct 495 ms 44792 KB Output is correct
89 Correct 469 ms 42488 KB Output is correct
90 Correct 485 ms 42488 KB Output is correct
91 Correct 457 ms 42744 KB Output is correct
92 Correct 481 ms 42440 KB Output is correct
93 Correct 484 ms 42488 KB Output is correct
94 Correct 473 ms 42360 KB Output is correct
95 Correct 465 ms 42616 KB Output is correct
96 Correct 451 ms 42488 KB Output is correct
97 Correct 480 ms 42616 KB Output is correct
98 Correct 455 ms 42616 KB Output is correct
99 Correct 458 ms 42616 KB Output is correct
100 Correct 498 ms 42708 KB Output is correct
101 Correct 454 ms 42620 KB Output is correct
102 Correct 480 ms 42488 KB Output is correct