제출 #1122561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122561		nhincc	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	34 ms	3144 KiB

fancyfence

/// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
/// Training ICPC 2024

#include<bits/stdc++.h>

/// #pragma GCC optimize("O3,unroll-loops")
/// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define fi first
#define se second
#define TASK "test"
#define pb push_back
#define EL cout << endl
#define Ti20_ntson int main()
#define in(x) cout << x << endl
#define all(x) (x).begin(),(x).end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FORD(i,l,r) for (int i = l; i >= r; i--)
#define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> vii;
typedef unsigned long long ull;
typedef vector<vector<int>> vvi;
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }

const int N = 1e5 + 5;
const int oo = INT_MAX;
const int mod = 1e9 + 7;
const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int n, Ans = 0;
pair<int, int> r[N];
tuple<int, int, int> a[N];

void Add(int &u, int v) {
    u += v;
    if (u >= mod) u -= mod;
}

void Del(int &u, int v) {
    u -= v;
    if (u < 0) u += mod;
}

long long Cost(long long x) {
    x %= mod;
    return (((x - 1) * x) / 2) % mod;
}

long long numRect(long long w, long long h) {
    return Cost(w + 1) * Cost(h + 1) % mod;
}

inline void Read_Input() {
    cin >> n;
    FOR(i, 1, n)
        cin >> r[i].fi;
    FOR(i, 1, n)
        cin >> r[i].se;

    FOR(i, 1, n)
        a[i] = {r[i].fi, r[i].se, i};
}

struct dsu {

    vector<long long> par;

    void sz(int n) {
        par.resize(n + 5);
        FOR(i, 1, n)
            par[i] = -r[i].se;
    }

    int Find(int u) {
        if (par[u] < 0) return u;
        par[u] = Find(par[u]);
        return par[u];
    }

    void Merge(int x, int y, int h) {
        x = Find(x);
        y = Find(y);
        if (x == y) return;

        Add(Ans, numRect(-par[x] - par[y], h));
        Del(Ans, numRect(-par[x], h));
        Del(Ans, numRect(-par[y], h));

        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }

}DSU;

inline void Solve() {
    vector<bool> is_used(n + 5, 0);
    sort(a + 1, a + n + 1);
    DSU.sz(n);
    FORD(i, n, 1) {
        auto[h, w, id] = a[i];
        Add(Ans, numRect(w, h));
        if (is_used[id + 1])
            DSU.Merge(id, id + 1, h);

        if (is_used[id - 1])
            DSU.Merge(id, id - 1, h);

        is_used[id] = true;
    }

    cout << Ans;
}

Ti20_ntson {
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T -- ) {
        Read_Input();
        Solve();
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27