oj.uz

Submission #2034

# Submission time Handle Problem Language Result Execution time Memory
2034 2013-07-19T20:44:02 Z solve 지우개 (GA4_eraser) C++
0 / 100
 30 ms 3328 KB 
#include <iostream>

using namespace std;

#define MOD 1000000007

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

long long 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, long long 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -