Submission #2033

#	Time	Username	Problem	Language	Result	Execution time	Memory
2033		solve	지우개 (GA4_eraser)	C++98	0 / 100	30 ms	3328 KiB

eraser

#include <iostream>

using namespace std;

#define MOD 1000000007

int N, A[100005];
long long tree1[100005], tree2[100005];

int read(long long * tree, int idx) {
  long long sum = 0;
  while(idx > 0) {
    sum += tree[idx];
    sum %= MOD;
    idx -= (idx & -idx);
  }
  return sum;
}

void update(long long * tree, int idx, int val) {
  while(idx <= N) {
    tree[idx] += val;
    tree[idx] %= MOD;
    idx += (idx & -idx);
  }
}

int main() {
  scanf("%d",&N);
  for(int i = 1;i<=N;i++) {
    scanf("%d",&A[i]);
  }
  sort(A + 1, A + 1 + N);
  long long res = 0;
  update(tree1, A[1], A[1]);
  for(int i = 2;i<=N;i++) {
    long long sum = read(tree1, A[i] - 1)%MOD;
    res += A[i] * read(tree2, A[i] - 1);
    res %= MOD;
    if(sum > 0) {
      update(tree2, A[i], (sum * A[i])%MOD);
    }
    update(tree1, A[i], A[i]);
  }
  cout<<res<<endl;
  return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 26
• Subtask 6: 0 / 28