답안 #47265 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47265	2018-04-30T04:37:05 Z	Talant	Boat (APIO16_boat)	C++17	31 / 100	1515 ms	252008 KB

boat

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #47265

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0