oj.uz

답안 #609457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609457 2022-07-27T15:58:17 Z SavicS Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 1 ms 340 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ldb;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;

#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
 
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 200005; 

int n;
array<int,3> niz[mxN];

bool bio[mxN];
int pom[mxN];

ll add(ll a, ll b){ a += b; if(a >= mod)a -= mod; return a; }
ll sub(ll a, ll b){ a -= b; if(a < 0)a += mod; return a; }
ll mul(ll a, ll b){ return (1ll * a * b) % mod; }

int len[mxN];
int par[mxN];
int L[mxN], R[mxN];
int findpar(int x){
    return (x == par[x] ? x : par[x] = findpar(par[x]));
}
void unite(int x, int y){
    x = findpar(x), y = findpar(y);
    if(x == y)return;
    if(len[x] < len[y])swap(x, y);
    par[y] = x; len[x] += len[y];
    L[x] = min(L[x], L[y]); R[x] = max(R[x], R[y]);
}
void init(){
    ff(i,1,n){
        par[i] = i;
        len[i] = niz[i][1];
        L[i] = i;
        R[i] = i;
    }
}

ll sum(int a){
    return (1ll * a * (a + 1) / 2) % mod; 
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    ff(i,1,n)cin >> niz[i][0], pom[i] = niz[i][0];
    ff(i,1,n)cin >> niz[i][1], niz[i][2] = i;

    init(); 

    sort(niz + 1, niz + n + 1);

    int j = n; ll rez = 0;
    fb(i,n,1){
        int h = niz[i][0];

        bio[niz[i][2]] = 1;
        while(j - 1 >= 1 && niz[j - 1][0] == h){
            j -= 1; bio[niz[j][2]] = 1;
        }

        ff(l,j,i){
            int X = niz[l][2];
            if(X > 1 && bio[X - 1] == 1)unite(X - 1, X);
            if(X < n && bio[X + 1] == 1)unite(X, X + 1);
        }

        set<int> s;
        ff(l,j,i)s.insert(findpar(niz[l][2]));

        for(auto c : s){
            int l = L[c];
            int r = R[c];
            int d = len[c];

            int mx = max(pom[l - 1], pom[r + 1]);

            ll kol = mul(sum(d), sub(sum(h), sum(mx)));
            rez = add(rez, kol);

        }


        i = j;

    }

    cout << rez << '\n';

    return 0;
}
/*



// probati bojenje sahovski
*/

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -