제출 #1289693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289693		am_aadvik	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	66 ms	9736 KiB

fancyfence

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>

#define int long long
const int maxn = 200005;
const int maxm = 505;
const int maxs = 2005;
const int mod = 1e9 + 7;
const int inf = 1e17;
using namespace std;

#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#endif

#if 0
class DSU {
public:
    vector<int> p, rank;
    DSU(int n) {
        p.resize(n), rank.resize(n, 1);
        for (int i = 0; i < n; ++i) p[i] = i;
    }

    int fset(int x) { return p[x] = ((p[x] == x) ? x : fset(p[x])); }
    bool iset(int x, int y) { return fset(x) == fset(y); }
    void uset(int x, int y) {
        x = fset(x), y = fset(y);
        if (x == y) return;
        if (rank[x] > rank[y]) swap(x, y);
        p[x] = y, rank[y] += rank[x];
    }
};
#endif

#if 0
class segtree {
private:
    vector<int> st, lazy, a;
    const int dv = 0;
    const int ldv = 0;
    int join(int l, int r) {
        return l + r;
    }
    int ljoin(int l, int r) {
        return l + r;
    }
    void upd(int s, int e, int node, int val) {
        if (val == ldv) return;
        st[node] += ((e - s + 1) * val);
    }

    int build(int s, int e, int node) {
        if (s == e)
            return st[node] = a[s];
        int mid = (s + e) / 2;
        return st[node] = join(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
    }

    void update(int s, int e, int node, int l, int r, int val) {
        if ((l > e) || (r < s)) return;
        if ((l <= s) && (r >= e)) {
            upd(s, e, node, val);
            lazy[node] = ljoin(lazy[node], val);
            return;
        }

        int mid = (s + e) / 2;
        upd(s, mid, node * 2, lazy[node]);
        upd(mid + 1, e, node * 2 + 1, lazy[node]);
        lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
        lazy[node] = ldv;

        update(s, mid, node * 2, l, r, val);
        update(mid + 1, e, node * 2 + 1, l, r, val);
        st[node] = join(st[node * 2], st[node * 2 + 1]);
    }

    int query(int s, int e, int node, int l, int r) {
        if ((l > e) || (r < s)) return dv;
        if ((l <= s) && (r >= e)) return st[node];

        int mid = (s + e) / 2;
        upd(s, mid, node * 2, lazy[node]);
        upd(mid + 1, e, node * 2 + 1, lazy[node]);
        lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
        lazy[node] = ldv;

        return join(query(s, mid, node * 2, l, r),
            query(mid + 1, e, node * 2 + 1, l, r));
    }

public:
    segtree(int n, vector<int> arr) {
        a = arr;
        st.resize(4 * n, dv);
        lazy.resize(4 * n, ldv);
        build(0, n - 1, 1);
    }

    int query(int l, int r) {
        return query(0, a.size() - 1, 1, l, r);
    }

    void update(int l, int r, int val) {
        update(0, a.size() - 1, 1, l, r, val);
    }
};
#endif

#if 0
int p[200005][20], dep[200005];
vector<int> g[200005];

void dfs(int node, int par) {
    p[node][0] = par;
    dep[node] = dep[par] + 1;
    for (int i = 1; i < 20; ++i)
        p[node][i] = p[p[node][i - 1]][i - 1];
    for (auto x : g[node])
        if (x != par) dfs(x, node);
}

int kpar(int node, int k) {
    for (int i = 0; i < 20; ++i)
        if (k & (1 << i))
            node = p[node][i];
    return node;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kpar(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int i = 19; i >= 0; --i)
        if (p[u][i] != p[v][i])
            u = p[u][i],
            v = p[v][i];
    return p[u][0];
}
#endif

#if 0
class line {
public:
    int m, c;
    line(int a = 0, int b = 0) { m = a, c = b; }
    int y(int x) { return m * x + c; }
};

class CHT {
private:
    int i = 0;
    vector<line> arr;

    bool bad(line a, line b, line c) {
        if (b.m == c.m) return b.c >= c.c;
        double x = (c.c - a.c) / (a.m - c.m);
        double y = (b.c - a.c) / (a.m - b.m);
        return ((y - x) > (double)(1e-6));
    }

public:
    void add(int m, int c) {
        line l(m, c);
        if (arr.size() < 2) {
            if (arr.size() == 1)
                if (arr.back().m == m)
                    if (arr.back().c >= c)
                        arr.pop_back();
            arr.push_back(l);
            return;
        }

        while (arr.size() > 1) {
            line pprev = arr[arr.size() - 2], prev = arr.back();
            if (!bad(pprev, prev, l)) break;
            arr.pop_back();
        }
        arr.push_back(l);
    }

    int query(int x) {
        if (arr.empty()) return inf;
        if (i >= arr.size()) i = arr.size() - 1;
        while (i < (arr.size() - 1)) {
            int cur = arr[i].y(x);
            int nxt = arr[i + 1].y(x);
            if (nxt > cur) break;
            ++i;
        }
        return arr[i].y(x);
    }
};
#endif

vector<int> rmx, cmx;
vector<vector<int>> a;
bool ispaek(int i, int j) {
    return ((rmx[i] == j) && (cmx[j] == i));
}
void problemA() {
    int n, m, q; cin >> n >> m >> q;
    rmx.assign(n, 0), cmx.assign(m, 0);
    a.assign(n, vector<int>(m, 0));
    for (auto& x : a) for (auto& y : x) cin >> y;
    for (int i = 0; i < n; ++i) {
        int mx = 0, mxj = 0;
        for (int j = 0; j < m; ++j)
            if (a[i][j] >= mx) mx = a[i][j], mxj = j;
        rmx[i] = mxj;
    }
    for (int j = 0; j < m; ++j) {
        int mx = 0, mxi = 0;
        for (int i = 0; i < n; ++i)
            if (a[i][j] >= mx) mx = a[i][j], mxi = i;
        cmx[j] = mxi;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            ans += ispaek(i, j);
    while (q--) {
        int i, j, val; cin >> i >> j >> val; --i, --j;
        int i1, j1, i2, j2;
        i1 = i, j1 = rmx[i];
        i2 = cmx[j], j2 = j;
        a[i][j] = val, ans -= ispaek(i, j);
        if (a[i1][j1] < a[i][j]) ans -= ispaek(i1, j1), rmx[i] = j;
        if (a[i2][j2] < a[i][j]) ans -= ispaek(i2, j2), cmx[j] = i;
        ans += ispaek(i, j);
        cout << ans << endl;
    }
}

int sum(int n) {
    return ((((n * (n + 1)) % mod) * 500000004) % mod);
}
int rsum(int l, int r, vector<int> &pre, vector<int>&w) {
    if (l > r) return 0;
    return (((pre[r] - pre[l] + mod) % mod) + w[l]) % mod;
}
//I have massive skill issue tbh
void problemB() {
    int n, mxd = 0, mnd = inf; cin >> n;
    vector<int> d(n), w(n), pre(n);
    for (auto& x : d) cin >> x;
    for (auto& x : w) cin >> x;
    vector<int> lens(n);
    set<int> b;
    b.insert(-1), b.insert(n);
    int ans = 0, prv = 0;
    vector<pair<int, int>> d2(n);
    for (int i = 0; i < n; ++i) d2[i] = { d[i], i };
    sort(d2.begin(), d2.end());

    int len = 0;
    for (auto x : w) len += x;
    for (int i = 0; i < n; ++i)
        pre[i] = (w[i] + (i == 0 ? 0 : pre[i - 1])) % mod;
    len %= mod, len = sum(len);
    for (int j = 0; j < n; ++j) {
        int i = d2[j].second, dep = d2[j].first;
        lens[i] = len;
        int nxt = *b.lower_bound(i);
        int prv = *prev(b.lower_bound(i));
        len = (len - sum(rsum(prv + 1, nxt - 1, pre, w)) + mod) % mod;
        len = (len + sum(rsum(prv + 1, i - 1, pre, w))) % mod;
        len = (len + sum(rsum(i + 1, nxt - 1, pre, w))) % mod;
        b.insert(i);
    }
    for (int i = 0; i < n; ++i) {
        int dep = d2[i].first, j = d2[i].second;
        ans = (ans + ((lens[j] * ((sum(dep) - sum(prv) + mod) % mod))) % mod) % mod;
        prv = dep;
    }
    cout << ans << endl;
}


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    //cin >> t;
    while (t--) {
        //problemA();
        problemB();
    }
    return 0;
}

• 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