oj.uz

Submission #47265

# Submission time Handle Problem Language Result Execution time Memory
47265 2018-04-30T04:37:05 Z Talant Boat (APIO16_boat) C++17
31 / 100
 1515 ms 252008 KB 
#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)2e6 + 7;

int n;
int a[N],b[N];
int ans,sz = 1;

struct node {
      int s,a;
      int l,r;
      node() {
            l = r = -1;
            s = 0,a = 0;
      }
};
node t[N * 2];

void update (int pos,int add,int v = 1,int tl = 0,int tr = 1e9) {
      if (tl == tr) {
            t[v].s += add;
            t[v].s %= inf;
      }
      else {
            int tm = (tl + tr) >> 1;
            if (pos <= tm) {
                  if (t[v].l == -1)
                        t[v].l = ++sz;
                  update (pos,add,t[v].l,tl,tm);
            }
            else {
                  if (t[v].r == -1)
                        t[v].r = ++sz;
                  update (pos,add,t[v].r,tm + 1,tr);
            }
            int m = 0,m1 = 0;
            if (t[v].l != -1)
                  m = t[t[v].l].s;

            if (t[v].r != -1)
                  m1 = t[t[v].r].s;
            t[v].s = (m + m1) % inf;
      }
}
int get (int l,int r,int v = 1,int tl = 0,int tr = 1e9) {
      if (tl > r || tr < l || v == -1)
            return 0;
      if (l <= tl && tr <= r)
            return (t[v].s % inf);
      int tm = (tl + tr) >> 1;

      return ((get(l,r,t[v].l,tl,tm) + get(l,r,t[v].r,tm + 1,tr)) % inf);
}
main () {
      cin >> n;

      for (int i = 1; i <= n; i ++)
            cin >> a[i] >> b[i];

      for (int i = 1; i <= n; i ++) {
            for (int j = b[i]; j >= a[i]; j --) {
                  int cur = get(0,j - 1);
                  update(j,cur + 1);
            }
      }
      cout << t[1].s % inf << endl;
}

Compilation message

boat.cpp:65:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 125560 KB Output is correct
2 Correct 86 ms 125668 KB Output is correct
3 Correct 86 ms 125732 KB Output is correct
4 Correct 88 ms 125756 KB Output is correct
5 Correct 87 ms 125756 KB Output is correct
6 Correct 87 ms 125756 KB Output is correct
7 Correct 87 ms 125856 KB Output is correct
8 Correct 87 ms 125856 KB Output is correct
9 Correct 88 ms 125872 KB Output is correct
10 Correct 89 ms 125900 KB Output is correct
11 Correct 89 ms 126040 KB Output is correct
12 Correct 88 ms 126040 KB Output is correct
13 Correct 86 ms 126040 KB Output is correct
14 Correct 88 ms 126040 KB Output is correct
15 Correct 100 ms 126156 KB Output is correct
16 Correct 88 ms 126156 KB Output is correct
17 Correct 88 ms 126156 KB Output is correct
18 Correct 95 ms 126156 KB Output is correct
19 Correct 86 ms 126156 KB Output is correct
20 Correct 87 ms 126164 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 125560 KB Output is correct
2 Correct 86 ms 125668 KB Output is correct
3 Correct 86 ms 125732 KB Output is correct
4 Correct 88 ms 125756 KB Output is correct
5 Correct 87 ms 125756 KB Output is correct
6 Correct 87 ms 125756 KB Output is correct
7 Correct 87 ms 125856 KB Output is correct
8 Correct 87 ms 125856 KB Output is correct
9 Correct 88 ms 125872 KB Output is correct
10 Correct 89 ms 125900 KB Output is correct
11 Correct 89 ms 126040 KB Output is correct
12 Correct 88 ms 126040 KB Output is correct
13 Correct 86 ms 126040 KB Output is correct
14 Correct 88 ms 126040 KB Output is correct
15 Correct 100 ms 126156 KB Output is correct
16 Correct 88 ms 126156 KB Output is correct
17 Correct 88 ms 126156 KB Output is correct
18 Correct 95 ms 126156 KB Output is correct
19 Correct 86 ms 126156 KB Output is correct
20 Correct 87 ms 126164 KB Output is correct
21 Correct 673 ms 126164 KB Output is correct
22 Correct 668 ms 126300 KB Output is correct
23 Correct 642 ms 126300 KB Output is correct
24 Correct 666 ms 126332 KB Output is correct
25 Correct 712 ms 126380 KB Output is correct
26 Correct 718 ms 126380 KB Output is correct
27 Correct 740 ms 126380 KB Output is correct
28 Correct 709 ms 126380 KB Output is correct
29 Correct 732 ms 126380 KB Output is correct
30 Correct 708 ms 126444 KB Output is correct
31 Correct 736 ms 126456 KB Output is correct
32 Correct 729 ms 126468 KB Output is correct
33 Correct 728 ms 126480 KB Output is correct
34 Correct 711 ms 126508 KB Output is correct
35 Correct 681 ms 126520 KB Output is correct
36 Correct 716 ms 126596 KB Output is correct
37 Correct 714 ms 126596 KB Output is correct
38 Correct 686 ms 126596 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1515 ms 252008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 125560 KB Output is correct
2 Correct 86 ms 125668 KB Output is correct
3 Correct 86 ms 125732 KB Output is correct
4 Correct 88 ms 125756 KB Output is correct
5 Correct 87 ms 125756 KB Output is correct
6 Correct 87 ms 125756 KB Output is correct
7 Correct 87 ms 125856 KB Output is correct
8 Correct 87 ms 125856 KB Output is correct
9 Correct 88 ms 125872 KB Output is correct
10 Correct 89 ms 125900 KB Output is correct
11 Correct 89 ms 126040 KB Output is correct
12 Correct 88 ms 126040 KB Output is correct
13 Correct 86 ms 126040 KB Output is correct
14 Correct 88 ms 126040 KB Output is correct
15 Correct 100 ms 126156 KB Output is correct
16 Correct 88 ms 126156 KB Output is correct
17 Correct 88 ms 126156 KB Output is correct
18 Correct 95 ms 126156 KB Output is correct
19 Correct 86 ms 126156 KB Output is correct
20 Correct 87 ms 126164 KB Output is correct
21 Correct 673 ms 126164 KB Output is correct
22 Correct 668 ms 126300 KB Output is correct
23 Correct 642 ms 126300 KB Output is correct
24 Correct 666 ms 126332 KB Output is correct
25 Correct 712 ms 126380 KB Output is correct
26 Correct 718 ms 126380 KB Output is correct
27 Correct 740 ms 126380 KB Output is correct
28 Correct 709 ms 126380 KB Output is correct
29 Correct 732 ms 126380 KB Output is correct
30 Correct 708 ms 126444 KB Output is correct
31 Correct 736 ms 126456 KB Output is correct
32 Correct 729 ms 126468 KB Output is correct
33 Correct 728 ms 126480 KB Output is correct
34 Correct 711 ms 126508 KB Output is correct
35 Correct 681 ms 126520 KB Output is correct
36 Correct 716 ms 126596 KB Output is correct
37 Correct 714 ms 126596 KB Output is correct
38 Correct 686 ms 126596 KB Output is correct
39 Runtime error 1515 ms 252008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -