oj.uz

Submission #541341

# Submission time Handle Problem Language Result Execution time Memory
541341 2022-03-23T07:05:12 Z nathanlee726 Fire (JOI20_ho_t5) C++14
100 / 100
 599 ms 49120 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;

//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif

int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod;
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

pii seg1[800010],seg2[800010];
int n,q,a[200010],b[200010],o[200010];
pair<pii,pii> que[200010];
vector<pair<pii,pii> > event;

inline void pull1(int p,int l,int r){
    int mi=(l+r)/2;
    seg1[p].X=seg1[p*2].X+seg1[p*2+1].X;
    seg1[p].Y=seg1[p*2+1].Y+seg1[p*2].Y+(r-mi)*seg1[p*2].X;
}

void build1(int p,int l,int r){
    if(l==r){
        if(b[l]>0)seg1[p].X=seg1[p].Y=b[l];
        return;
    }
    int mi=(l+r)/2;
    build1(p*2,l,mi),build1(p*2+1,mi+1,r);
    pull1(p,l,r);
    return;
}

void modify1(int p,int l,int r,int x,int v){
    if(l==r){
        seg1[p]={v,v};
        return;
    }
    int mi=(l+r)/2;
    if(mi>=x)modify1(p*2,l,mi,x,v);
    else modify1(p*2+1,mi+1,r,x,v);
    pull1(p,l,r);
}

pii query1(int p,int l,int r,int ql,int qr){
    if(l>qr||r<ql)return {0,0};
    if(l>=ql&&r<=qr)return seg1[p];
    int mi=(l+r)/2;
    pii t1=query1(p*2,l,mi,ql,qr),t2=query1(p*2+1,mi+1,r,ql,qr);
    if(ql>mi)return t2;
    else if(qr<=mi)return t1;
    else{
        if(qr<=r){t2.Y+=(t1.Y+(qr-mi)*t1.X);t2.X+=t1.X;}
        else{t2.Y+=(t1.Y+(r-mi)*t1.X);t2.X+=t1.X;}
        return t2;
    }
}

///////////////////////////////////////////////

inline void pull2(int p,int l,int r){
    int mi=(l+r)/2;
    seg2[p].X=seg2[p*2].X+seg2[p*2+1].X;
    seg2[p].Y=seg2[p*2+1].Y+seg2[p*2].Y+(r-mi)*seg2[p*2].X;
}

void build2(int p,int l,int r){
    if(l==r){
        if(b[l]<0)seg2[p].X=seg2[p].Y=b[l];
        return;
    }
    int mi=(l+r)/2;
    build2(p*2,l,mi),build2(p*2+1,mi+1,r);
    pull2(p,l,r);
    return;
}

void modify2(int p,int l,int r,int x,int v){
    if(l==r){
        seg2[p]={v,v};
        return;
    }
    int mi=(l+r)/2;
    if(mi>=x)modify2(p*2,l,mi,x,v);
    else modify2(p*2+1,mi+1,r,x,v);
    pull2(p,l,r);
}

pii query2(int p,int l,int r,int ql,int qr){
    if(l>qr||r<ql)return {0,0};
    if(l>=ql&&r<=qr){return seg2[p];}
    int mi=(l+r)/2;
    pii t1=query2(p*2,l,mi,ql,qr),t2=query2(p*2+1,mi+1,r,ql,qr);
    if(ql>mi)return t2;
    else if(qr<=mi){return t1;}
    else{
        if(qr<=r){t2.Y+=(t1.Y+(qr-mi)*t1.X);t2.X+=t1.X;}
        else{t2.Y+=(t1.Y+(r-mi)*t1.X);t2.X+=t1.X;}
        return t2;
    }
}

signed main(){
	IOS();
    cin>>n>>q;
    F(n)cin>>a[i];
    b[0]=a[0];
    F(n-1)b[i+1]=a[i+1]-a[i];
    F(n)bug(b[i]);
    build1(1,0,n-1);
    build2(1,0,n-1);
    F(q){
        int t,l,r;
        cin>>t>>l>>r;
        --l,--r;
        que[i]={{t,i},{l,r}};
    }
    vector<pii> qu;
    qu.pb({a[n-1],n-1});
    for(int i=n-1;i>0;i--){
        while(sz(qu)&&qu.back().X<a[i-1])qu.pop_back();
        if(b[i]<0){
            if(sz(qu)){
                int tt=qu.back().Y-i;
                event.pb({{tt,1},{qu.back().Y,qu.back().X-a[i-1]}});
                event.pb({{tt,2},{i,0}});
            }
        }
        qu.pb({a[i-1],i-1});
    }
    qu.clear();
    qu.pb({a[0],0});
    for(int i=1;i<=n-1;i++){
        while(sz(qu)&&qu.back().X<a[i])qu.pop_back();
        if(b[i]>0){
            if(sz(qu)){
                int tt=i-qu.back().Y-1;
                event.pb({{tt,1},{i,0}});
                event.pb({{tt,2},{qu.back().Y+1,a[i]-qu.back().X}});
            }
        }
        qu.pb({a[i],i});
    }
    sort(all(event));
    sort(que,que+q);
    //F(sz(event))cout<<event[i].X.X<<" "<<event[i].X.Y<<" "<<event[i].Y.X<<" "<<event[i].Y.Y<<endl;
    //bug(query2(1,0,n-1,0,1).Y);
    int p=0;
    F(q){
        while(p<sz(event)&&event[p].X.X<=que[i].X.X){
            if(event[p].X.Y==1){
                modify1(1,0,n-1,event[p].Y.X,event[p].Y.Y);
            }
            else{
                modify2(1,0,n-1,event[p].Y.X,event[p].Y.Y);
            }
            p++;
        }
        int ss=0;
        bug(p);
        if(que[i].Y.X>0)ss+=(query1(1,0,n-1,0,que[i].Y.X-1).X*(que[i].Y.Y-que[i].Y.X+1));
        bug(que[i].X.Y,ss);
        bug(query1(1,0,n-1,que[i].Y.X,que[i].Y.Y).X);
        ss+=query1(1,0,n-1,que[i].Y.X,que[i].Y.Y).Y;
        bug(que[i].X.Y,ss);
        int l=que[i].Y.X-que[i].X.X,r=que[i].Y.Y-que[i].X.X;
        if(r>=0){
            if(l>0){
                ss+=(query2(1,0,n-1,0,l-1).X*(r-l+1));
            }
            bug(que[i].X.Y,ss);
            l=max(0ll,l);
            bug(l,r);
            bug(query2(1,0,n-1,l,r).X);
            ss+=query2(1,0,n-1,l,r).Y;
            bug(que[i].X.Y,ss);
        }
        o[que[i].X.Y]=ss;
    }
    F(q)cout<<o[i]<<endl;
	return 0;
}
/*
9 3 2 6 5
9 -6 -1 4 -1

9 0 0 4 0
0 -6 -1 0 -1

9 9 3 6 6
9 0 -6 3 0

9 0 0 3 0
0 0 -6 0 0

9 9 9 6 6
9 0 0 -3 0

9 0 0 0 0
0 0 0 -3 0

*/

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:19:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 | #define Fl(i,l,n) for(int i=l;i<n;i++)
      |                   ^~~
ho_t5.cpp:18:17: note: in expansion of macro 'Fl'
   18 | #define Fi(i,n) Fl(i,0,n)
      |                 ^~
ho_t5.cpp:17:14: note: in expansion of macro 'Fi'
   17 | #define F(n) Fi(i,n)
      |              ^~
ho_t5.cpp:239:5: note: in expansion of macro 'F'
  239 |     F(q)cout<<o[i]<<endl;
      |     ^
ho_t5.cpp:240:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  240 |  return 0;
      |  ^~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 454 ms 48284 KB Output is correct
3 Correct 370 ms 48092 KB Output is correct
4 Correct 584 ms 48356 KB Output is correct
5 Correct 445 ms 47068 KB Output is correct
6 Correct 514 ms 46928 KB Output is correct
7 Correct 532 ms 47260 KB Output is correct
8 Correct 466 ms 47452 KB Output is correct
9 Correct 599 ms 47280 KB Output is correct
10 Correct 488 ms 46736 KB Output is correct
11 Correct 412 ms 47384 KB Output is correct
12 Correct 457 ms 46728 KB Output is correct
13 Correct 513 ms 47092 KB Output is correct
14 Correct 484 ms 47000 KB Output is correct
15 Correct 479 ms 47176 KB Output is correct
16 Correct 590 ms 46892 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 412 ms 48316 KB Output is correct
3 Correct 386 ms 46712 KB Output is correct
4 Correct 467 ms 46960 KB Output is correct
5 Correct 478 ms 46636 KB Output is correct
6 Correct 450 ms 46888 KB Output is correct
7 Correct 489 ms 46996 KB Output is correct
8 Correct 530 ms 47228 KB Output is correct
9 Correct 449 ms 47400 KB Output is correct
10 Correct 471 ms 47228 KB Output is correct
11 Correct 493 ms 47524 KB Output is correct
12 Correct 460 ms 47180 KB Output is correct
13 Correct 496 ms 47484 KB Output is correct
14 Correct 482 ms 47300 KB Output is correct
15 Correct 456 ms 47376 KB Output is correct
16 Correct 454 ms 47164 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 40344 KB Output is correct
2 Correct 472 ms 41128 KB Output is correct
3 Correct 552 ms 42672 KB Output is correct
4 Correct 504 ms 42464 KB Output is correct
5 Correct 493 ms 41864 KB Output is correct
6 Correct 499 ms 40104 KB Output is correct
7 Correct 468 ms 42360 KB Output is correct
8 Correct 479 ms 40428 KB Output is correct
9 Correct 476 ms 42388 KB Output is correct
10 Correct 449 ms 40552 KB Output is correct
11 Correct 468 ms 41500 KB Output is correct
12 Correct 470 ms 41520 KB Output is correct
13 Correct 489 ms 40652 KB Output is correct
14 Correct 417 ms 40948 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 328 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 454 ms 48284 KB Output is correct
34 Correct 370 ms 48092 KB Output is correct
35 Correct 584 ms 48356 KB Output is correct
36 Correct 445 ms 47068 KB Output is correct
37 Correct 514 ms 46928 KB Output is correct
38 Correct 532 ms 47260 KB Output is correct
39 Correct 466 ms 47452 KB Output is correct
40 Correct 599 ms 47280 KB Output is correct
41 Correct 488 ms 46736 KB Output is correct
42 Correct 412 ms 47384 KB Output is correct
43 Correct 457 ms 46728 KB Output is correct
44 Correct 513 ms 47092 KB Output is correct
45 Correct 484 ms 47000 KB Output is correct
46 Correct 479 ms 47176 KB Output is correct
47 Correct 590 ms 46892 KB Output is correct
48 Correct 412 ms 48316 KB Output is correct
49 Correct 386 ms 46712 KB Output is correct
50 Correct 467 ms 46960 KB Output is correct
51 Correct 478 ms 46636 KB Output is correct
52 Correct 450 ms 46888 KB Output is correct
53 Correct 489 ms 46996 KB Output is correct
54 Correct 530 ms 47228 KB Output is correct
55 Correct 449 ms 47400 KB Output is correct
56 Correct 471 ms 47228 KB Output is correct
57 Correct 493 ms 47524 KB Output is correct
58 Correct 460 ms 47180 KB Output is correct
59 Correct 496 ms 47484 KB Output is correct
60 Correct 482 ms 47300 KB Output is correct
61 Correct 456 ms 47376 KB Output is correct
62 Correct 454 ms 47164 KB Output is correct
63 Correct 565 ms 40344 KB Output is correct
64 Correct 472 ms 41128 KB Output is correct
65 Correct 552 ms 42672 KB Output is correct
66 Correct 504 ms 42464 KB Output is correct
67 Correct 493 ms 41864 KB Output is correct
68 Correct 499 ms 40104 KB Output is correct
69 Correct 468 ms 42360 KB Output is correct
70 Correct 479 ms 40428 KB Output is correct
71 Correct 476 ms 42388 KB Output is correct
72 Correct 449 ms 40552 KB Output is correct
73 Correct 468 ms 41500 KB Output is correct
74 Correct 470 ms 41520 KB Output is correct
75 Correct 489 ms 40652 KB Output is correct
76 Correct 417 ms 40948 KB Output is correct
77 Correct 549 ms 48144 KB Output is correct
78 Correct 528 ms 48760 KB Output is correct
79 Correct 474 ms 48436 KB Output is correct
80 Correct 514 ms 48140 KB Output is correct
81 Correct 488 ms 47980 KB Output is correct
82 Correct 502 ms 48316 KB Output is correct
83 Correct 532 ms 48208 KB Output is correct
84 Correct 541 ms 48184 KB Output is correct
85 Correct 467 ms 48348 KB Output is correct
86 Correct 474 ms 48280 KB Output is correct
87 Correct 409 ms 48876 KB Output is correct
88 Correct 434 ms 48724 KB Output is correct
89 Correct 380 ms 48156 KB Output is correct
90 Correct 424 ms 48696 KB Output is correct
91 Correct 445 ms 48068 KB Output is correct
92 Correct 396 ms 48028 KB Output is correct
93 Correct 424 ms 48160 KB Output is correct
94 Correct 417 ms 49120 KB Output is correct
95 Correct 394 ms 48788 KB Output is correct
96 Correct 418 ms 48512 KB Output is correct
97 Correct 407 ms 48364 KB Output is correct
98 Correct 532 ms 47696 KB Output is correct
99 Correct 542 ms 47912 KB Output is correct
100 Correct 541 ms 48148 KB Output is correct
101 Correct 548 ms 47892 KB Output is correct
102 Correct 524 ms 48436 KB Output is correct