Submission #67007294

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

struct Seg1{
    mint tree[800800], lazy[800800];
    void init(int i, int l, int r){
        lazy[i] = 1;
        tree[i] = 0;
        if (l==r) return;

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void push(int i, int l, int r){
        if (lazy[i]==1) return;
        tree[i] *= lazy[i];
        if (l!=r){
            lazy[i<<1] *= lazy[i];
            lazy[i<<1|1] *= lazy[i];
        }
        lazy[i] = 1;
    }
    void mul(int i, int l, int r, int s, int e, mint x){
        push(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] *= x;
            push(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        mul(i<<1, l, m, s, e, x); mul(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void set(int i, int l, int r, int p, mint x){
        push(i, l, r);
        if (r<p || p<l) return;
        if (l==r){
            tree[i] = x;
            return;
        }

        int m = (l+r)>>1;
        set(i<<1, l, m, p, x); set(i<<1|1, m+1, r, p, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    mint query(int i, int l, int r, int s, int e){
        push(i, l, r);
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i];

        int m = (l+r)>>1;
        return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
    }
}tree1;

struct Seg2{
    int tree[800800], sz;
    void init(int n){
        sz = n;
        fill(tree, tree+sz*2, 0);
    }
    void update(int p, int x){
        for (p+=sz;p;p>>=1) tree[p] += x;
    }
    int query(int l, int r){
        ++r;
        int ret = 0;
        for (l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if (l&1) ret += tree[l++];
            if (r&1) ret += tree[--r];
        }
        return ret;
    }
}tree2;

mint pw[200200];
array<int, 4> a[200200];

mint solve(int n){
    mint ret = 0;
    sort(a+1, a+n+1);

    tree1.init(1, 1, n);
    tree2.init(n+1);

    for (int i=1;i<=n;i++){
        int cnt = tree2.query(1, a[i][1]);
        mint val = tree1.query(1, 1, n, a[i][1], n);
        val += pw[cnt] * a[i][3];
        ret += val * a[i][2];

        tree1.mul(1, 1, n, a[i][1], n, 2);
        tree1.set(1, 1, n, a[i][1], pw[cnt] * a[i][3]);
        tree2.update(a[i][1], 1);
    }

    return ret;
}

int main(){
    int n;
    scanf("%d", &n);

    pw[0] = 1;
    for (int i=1;i<=n;i++) pw[i] = pw[i-1] * 2;

    for (int i=1;i<=n;i++){
        a[i][0] = i;
        scanf("%d", &a[i][1]);
        a[i][2] = i, a[i][3] = a[i][1];
    }
    mint ans = solve(n);

    for (int i=1;i<=n;i++) a[i][0] = n+1-a[i][0];
    ans -= solve(n);

    for (int i=1;i<=n;i++) a[i][1] = n+1-a[i][1];
    ans += solve(n);

    for (int i=1;i<=n;i++) a[i][0] = n+1-a[i][0];
    ans -= solve(n);

    printf("%d\n", ans.val());
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:109:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  109 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:116:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |         scanf("%d", &a[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Judge Result