oj.uz

Submission #792450

# Submission time Handle Problem Language Result Execution time Memory
792450 2023-07-25T05:06:41 Z 반딧불(#10051) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 0 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1000003;

void input();
void makeGoal();
void makeTree();
void solve();

int main(){
    input();
    makeGoal();
    makeTree();
    solve();
}

int n;
ll arr[1000002];
ll goal[1000002];

void input(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
}

int L;
int numbers[1000002];
int peak;
ll prfMax[1000002], sufMax[1000002];
void makeGoal(){
    for(int i=1; i<=n; i++) prfMax[i] = max(prfMax[i-1], arr[i]);
    for(int i=n; i>=1; i--) sufMax[i] = max(sufMax[i+1], arr[i]);
    for(int i=1; i<=n; i++){
        goal[i] = arr[i];
        if(prfMax[i-1] > arr[i] && sufMax[i+1] > arr[i]) goal[i] = min(prfMax[i-1], sufMax[i+1]);
    }

    for(int i=1; i<=n; i++) numbers[i] = arr[i];
    sort(numbers+1, numbers+n+1);
    L = unique(numbers+1, numbers+n+1) - numbers - 1;
}

struct segTree{
    ll minVal[1<<21], minCnt[1<<21], secondMin[1<<21], lazy[1<<21];

    inline void merge(int i){
        minVal[i] = min(minVal[i*2], minVal[i*2+1]);
        minCnt[i] = (minVal[i] == minVal[i*2] ? minCnt[i*2] : 0) + (minVal[i] == minVal[i*2+1] ? minCnt[i*2+1] : 0);
        secondMin[i] = min(minVal[i] == minVal[i*2] ? secondMin[i*2] : minVal[i*2],
                           minVal[i] == minVal[i*2+1] ? secondMin[i*2+1] : minVal[i*2+1]);
    }

    void init(int i, int l, int r, ll *A){
        if(l==r){
            minVal[i] = A[l], minCnt[i] = 1;
            secondMin[i] = INF;
            lazy[i] = 0;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        merge(i);
    }

    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        minVal[i] = max(minVal[i], lazy[i]);
        if(l!=r){
            lazy[i*2] = max(lazy[i*2], lazy[i]);
            lazy[i*2+1] = max(lazy[i*2+1], lazy[i]);
        }
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l || minVal[i] >= v) return;
        if(s<=l && r<=e && v < secondMin[i]){
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    pair<ll, ll> query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return make_pair(INF, 0);
        if(s<=l && r<=e) return make_pair(minVal[i], minCnt[i]);
        int m = (l+r)>>1;
        pair<ll, ll> a = query(i*2, l, m, s, e), b = query(i*2+1, m+1, r, s, e);
        return make_pair(min(a.first, b.first), (a.first<=b.first?a.second:0) + (b.first<=a.first?b.second:0));
    }

    int getLeftest(int i, int l, int r, int x, ll v){
        propagate(i, l, r);
        if(r<x || minVal[i] > v) return r+1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = getLeftest(i*2, l, m, x, v);
        if(tmp != m+1) return tmp;
        else return getLeftest(i*2+1, m+1, r, x, v);
    }

    int getRightest(int i, int l, int r, int x, ll v){
        propagate(i, l, r);
        if(x<l || minVal[i] > v) return l-1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = getRightest(i*2+1, m+1, r, x, v);
        if(tmp != m) return tmp;
        else return getRightest(i*2, l, m, x, v);
    }

    ll secondQuery(int i, int l, int r, int s, int e, ll v){
        if(r<s || e<l) return INF;
        if(s<=l && r<=e) return minVal[i] == v ? secondMin[i] : minVal[i];
        int m = (l+r)>>1;
        return min(secondQuery(i*2, l, m, s, e, v), secondQuery(i*2+1, m+1, r, s, e, v));
    }
} tree;

void makeTree(){
    tree.init(1, 1, n, arr);
}

ll sum1(ll s){
    return s*(s+1)/2%MOD;
}

ll sum1(ll s, ll e){
    return (sum1(e) - sum1(s-1) + MOD) % MOD;
}

ll ans;
void solve(){
    int lpnt = 1, rpnt = n;
    for(int a=1; a<L; a++){
        ll s = numbers[a], e = numbers[a+1]; /// �������� ������
        while(goal[lpnt] < e) lpnt++;
        while(goal[rpnt] < e) rpnt--;

        pair<ll, ll> pr = tree.query(1, 1, n, lpnt, rpnt);
        if(pr.first != s) continue;
        int k = pr.second;
        int l = tree.getLeftest(1, 1, n, lpnt, s);
        int r = tree.getRightest(1, 1, n, rpnt, s);
        ll lv = tree.query(1, 1, n, lpnt, l-1).first;
        ll rv = tree.query(1, 1, n, r+1, rpnt).first;
        ll mv = tree.secondQuery(1, 1, n, l+1, r-1, s);

        if(l==r){ /// �ٲ� �� �ϳ��� ���
            ans += (e-s) * (lv + rv) + sum1(s, e-1);
            ans %= MOD;
        }
        else{ /// �ٲ� �� ���� ���� ���
            if(lv > rv) swap(lv, rv);
            ans += (lv + rv + min({lv, rv, mv})) * (e-s);
            ans += sum1(s, e-1) + (e-s);
            ans += sum1(s+1, e) * 2 * (k-2);
            ans += sum1(s, e-1) * k;
            ans %= MOD;
        }

        tree.update(1, 1, n, lpnt, rpnt, e);
    }
    printf("%lld", ans);
}

Compilation message

Main.cpp: In function 'void input()':
Main.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:27:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 3.0

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

Subtask #4
0 / 3.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 4.0

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