oj.uz

Submission #968135

# Submission time Handle Problem Language Result Execution time Memory
968135 2024-04-23T07:54:19 Z owoovo Real Mountains (CCO23_day1problem2) C++17
0 / 25
 37 ms 49496 KB 
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
const ll p=1e6+3;
const ll maxn=1e9;
struct node{
    ll val=0,tag1=maxn,tag2=0;
}tri[4000010];
void init(ll l,ll r,int id){
    tri[id].val=0,tri[id].tag1=maxn,tri[id].tag2=0;
    if(l==r)return;
    ll m=(l+r)>>1;
    init(l,m,id*2+1);
    init(m+1,r,id*2+2);
    return;
}
void push(ll l,ll r,int id){
    //cout<<l<<" "<<r<<" "<<id<<" ";
    if(tri[id].tag2!=0){
        //cout<<"2\n";
        tri[id].val=((r-l+1)*(r+l)/2)%p;
    }else if(tri[id].tag1<maxn){
        //cout<<"1\n";
        tri[id].val=((r-l+1)*tri[id].tag1)%p;
    }
    if(l!=r){
        tri[id*2+1].tag1=min(tri[id].tag1,tri[id*2+1].tag1);
        tri[id*2+2].tag1=min(tri[id].tag1,tri[id*2+2].tag1);
        tri[id*2+1].tag2|=tri[id].tag2;
        tri[id*2+2].tag2|=tri[id].tag2;
    }
}
void pull(ll l,ll r,int id){
    if(l!=r){
        ll m=(l+r)>>1;
        push(l,m,id*2+1);
        push(m+1,r,id*2+2);
    }
    tri[id].val=(tri[id*2+1].val+tri[id*2+2].val)%p;
    return;
}
void modify1(int l,int r,int L,int R,int id,ll x){
    push(l,r,id);
    if(l==L&&r==R){
        tri[id].tag1=min(tri[id].tag1,x);
        push(l,r,id);
        return;
    }
    int m=(l+r)>>1;
    if(R<=m)modify1(l,m,L,R,id*2+1,x);
    else if(m<L)modify1(m+1,r,L,R,id*2+2,x);
    else {
        modify1(l,m,L,m,id*2+1,x);
        modify1(m+1,r,m+1,R,id*2+2,x);
    }
    pull(l,r,id);
    return;
}
void modify2(int l,int r,int L,int R,int id){
    push(l,r,id);
    if(l==L&&r==R){
        tri[id].tag2=1;
        push(l,r,id);
        return;
    }
    int m=(l+r)>>1;
    if(R<=m)modify2(l,m,L,R,id*2+1);
    else if(m<L)modify2(m+1,r,L,R,id*2+2);
    else {
        modify2(l,m,L,m,id*2+1);
        modify2(m+1,r,m+1,R,id*2+2);
    }
    pull(l,r,id);
    return ;
}
ll query(int l, int r, int L,int R,int id){
    push(l,r,id);
    if(l==L&&r==R){
        return tri[id].val;
    }
    int m=(l+r)>>1;
    if(R<=m)return query(l,m,L,R,id*2+1);
    else if(m<L)return query(m+1,r,L,R,id*2+2);
    else {
        return (query(l,m,L,m,id*2+1)+query(m+1,r,m+1,R,id*2+2))%p;
    }
}
ll ans;
int n,h[1000010],mh;
vector<pair<int,int>> seg,bseg;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i],mh=max(mh,h[i]);
    ll pos=1,mx=0;
    while(h[pos]!=mh){
        if(h[pos]>mx){
            mx=h[pos];
        }
        seg.push_back({h[pos],mx});
        ans+=(mx-h[pos])*(mx+h[pos]-1)/2;
        ans%=p;
        pos++;
    }
    ll bpos=n,bmx=0;
    while(h[bpos]!=mh){
        if(h[bpos]>bmx){
            bmx=h[bpos];
        }
        bseg.push_back({h[bpos],bmx});
        ans+=(bmx-h[bpos])*(bmx+h[bpos]-1)/2;
        ans%=p;
        bpos--;
    }
    for(int i=pos;i<=bpos;i++){
        seg.push_back({h[i],mh});
        ans+=(mh-h[i])*(mh+h[i]-1)/2;
        ans%=p;
    }

    reverse(bseg.begin(),bseg.end());
    for(int i=0;i<bseg.size();i++)seg.push_back(bseg[i]);

    
    init(1,1000000,0);
    for(int i=0;i<n;i++){
       // cout<<seg[i].F<<" "<<seg[i].S<<"\n";
        if(seg[i].F!=seg[i].S){
            //cout<<query(1,1000000,seg[i].F+1,seg[i].S,0)<<"F\n";
            ans+=query(1,1000000,seg[i].F+1,seg[i].S,0);
            modify2(1,1000000,seg[i].F+1,seg[i].S,0);
            ans%=p;
        }
        modify1(1,1000000,1,seg[i].F,0,seg[i].F);
    }
    reverse(seg.begin(),seg.end());
    init(1,1000000,0);
    for(int i=0;i<n;i++){
        //cout<<seg[i].F<<" "<<seg[i].S<<" "<<query(1,1000000,3,3,0)<<"\n";
        if(seg[i].F!=seg[i].S){
           // cout<<query(1,1000000,seg[i].F+1,seg[i].S,0)<<"B\n";
            ans+=query(1,1000000,seg[i].F+1,seg[i].S,0);
            modify2(1,1000000,seg[i].F+1,seg[i].S,0);
            ans%=p;
        }
        modify1(1,1000000,1,seg[i].F,0,seg[i].F);
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<bseg.size();i++)seg.push_back(bseg[i]);
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 3.0

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

Subtask #4
0 / 3.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 4.0

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