답안 #48375 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48375	2018-05-12T09:54:37 Z	temurbek_khujaev	Boat (APIO16_boat)	C++17	31 / 100	2000 ms	251756 KB

boat

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
#define fi first
#define se second

typedef long double 	ld;
typedef long long 		ll;
typedef vector<int> 	VI;
typedef pair<int, int>	PII;
typedef pair<ll, ll> 	PLL;
typedef vector<ll>		VL;
typedef vector<PLL> 	VPL;
typedef vector<PII> 	VPI;
typedef tree <int, null_type, less<int> ,rb_tree_tag ,tree_order_statistics_node_update > ordered_set;

#define REP(i,a,n) for (int i = a; i < n; i++)
#define PER(i,a,n) for (int i = n-1; i >= a; i--)

#define dbb(x) cout << #x << " = " << x << "\t";
#define db(x)        { dbb(x); cout << endl; }
#define db2(x,y)     { dbb(x); dbb(y); cout << endl; }
#define db3(x,y,z)   { dbb(x); dbb(y); dbb(z); cout << endl; }

template <typename t1, typename t2> inline bool upmax(t1 &a, t2 b) { if (a<(t1)b) { a = (t1)b; return true; } else return false; }
template <typename t1, typename t2> inline bool upmin(t1 &a, t2 b) { if (a>(t1)b) { a = (t1)b; return true; } else return false; }
template <typename T> inline bool pal(T &x){ int n = SZ(x); REP(i, 0, n / 2) { if (x[i] != x[n - i - 1]) return 0; } return 1; }
template <typename T> inline T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template <typename T> inline T lcm(T a, T b) { return a*(b / gcd(a, b)); }
template <typename T> inline T sqr(T a) { return a*a; }

int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };

const int INF = 1000000404;
const ll  LINF = 4000000000000000404ll;
const ll  MOD = 1000000007ll;
const ld  PI = acos(-1.0);
const ld  EPS = 1e-9;

ll powmod(ll a, ll b) {
	ll res = 1; a %= MOD; assert(b >= 0);
	for (; b; b >>= 1) { if (b & 1) res = res*a%MOD; a = a*a%MOD; }return res;
}

int SQ = 404;
int timer = 0;

#define N 555

int a[N];
int b[N];
ll comb[N];

struct node{
    node *l,*r;
    ll val = 0;
    node(){
        l = r = NULL;
        val = 0;
    }
};

void update(node *v, int pos, ll delta, int tl = 0,int tr = INF) {
    v->val += delta;
    v->val %= MOD;

    //db2(tl,tr);
    //db(v->val);
    if (tl == tr) {
        return;
    } else {
        if (v->l == NULL) v->l = new node();
        if (v->r == NULL) v->r = new node();

        int tm = (tl + tr) >> 1;
        if (pos <= tm) update(v->l, pos, delta, tl, tm);
        else update(v->r, pos, delta, tm + 1, tr);
    }
}

ll get(int r,node *v,int tl = 0,int tr = INF) {

    if (v == NULL || tl > r) return 0;

    if (tr <= r) return v->val;

    int tm = (tl + tr) >> 1;

    return (get(r, v->l , tl , tm ) + get(r, v->r , tm + 1, tr)) % MOD;
}


void solve() {
    int n;
    cin >> n;

    node * v = new node();

    REP (i, 1, n + 1) {
        cin >> a[i] >> b[i];
    }
    ll ans = 0;
    REP (i, 1, n + 1) {

        PER(j, a[i], b[i] + 1) {
            ll s = get(j - 1, v);
        //    db(s);
            update(v, j, s + 1);
        }

    }
    cout << get(INF, v) << endl;

}

int main()
{
  //  freopen("INPUT.in","r",stdin);
  //  freopen("OUTPUT.out","w",stdout);

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

Compilation message

boat.cpp: In function 'void solve()':
boat.cpp:111:8: warning: unused variable 'ans' [-Wunused-variable]
     ll ans = 0;
        ^~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1016 KB	Output is correct
2	Correct	3 ms	1016 KB	Output is correct
3	Correct	3 ms	1200 KB	Output is correct
4	Correct	3 ms	1200 KB	Output is correct
5	Correct	4 ms	1200 KB	Output is correct
6	Correct	3 ms	1232 KB	Output is correct
7	Correct	3 ms	1232 KB	Output is correct
8	Correct	3 ms	1232 KB	Output is correct
9	Correct	3 ms	1232 KB	Output is correct
10	Correct	3 ms	1232 KB	Output is correct
11	Correct	3 ms	1232 KB	Output is correct
12	Correct	3 ms	1344 KB	Output is correct
13	Correct	3 ms	1344 KB	Output is correct
14	Correct	3 ms	1344 KB	Output is correct
15	Correct	3 ms	1344 KB	Output is correct
16	Correct	2 ms	1344 KB	Output is correct
17	Correct	2 ms	1344 KB	Output is correct
18	Correct	2 ms	1344 KB	Output is correct
19	Correct	2 ms	1344 KB	Output is correct
20	Correct	3 ms	1344 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1016 KB	Output is correct
2	Correct	3 ms	1016 KB	Output is correct
3	Correct	3 ms	1200 KB	Output is correct
4	Correct	3 ms	1200 KB	Output is correct
5	Correct	4 ms	1200 KB	Output is correct
6	Correct	3 ms	1232 KB	Output is correct
7	Correct	3 ms	1232 KB	Output is correct
8	Correct	3 ms	1232 KB	Output is correct
9	Correct	3 ms	1232 KB	Output is correct
10	Correct	3 ms	1232 KB	Output is correct
11	Correct	3 ms	1232 KB	Output is correct
12	Correct	3 ms	1344 KB	Output is correct
13	Correct	3 ms	1344 KB	Output is correct
14	Correct	3 ms	1344 KB	Output is correct
15	Correct	3 ms	1344 KB	Output is correct
16	Correct	2 ms	1344 KB	Output is correct
17	Correct	2 ms	1344 KB	Output is correct
18	Correct	2 ms	1344 KB	Output is correct
19	Correct	2 ms	1344 KB	Output is correct
20	Correct	3 ms	1344 KB	Output is correct
21	Correct	350 ms	1344 KB	Output is correct
22	Correct	358 ms	1344 KB	Output is correct
23	Correct	330 ms	1344 KB	Output is correct
24	Correct	363 ms	1344 KB	Output is correct
25	Correct	376 ms	1344 KB	Output is correct
26	Correct	389 ms	1344 KB	Output is correct
27	Correct	387 ms	1344 KB	Output is correct
28	Correct	384 ms	1344 KB	Output is correct
29	Correct	391 ms	1344 KB	Output is correct
30	Correct	510 ms	62588 KB	Output is correct
31	Correct	482 ms	62588 KB	Output is correct
32	Correct	494 ms	62604 KB	Output is correct
33	Correct	499 ms	62604 KB	Output is correct
34	Correct	522 ms	62604 KB	Output is correct
35	Correct	476 ms	62604 KB	Output is correct
36	Correct	497 ms	62604 KB	Output is correct
37	Correct	483 ms	62604 KB	Output is correct
38	Correct	529 ms	62604 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2085 ms	251756 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1016 KB	Output is correct
2	Correct	3 ms	1016 KB	Output is correct
3	Correct	3 ms	1200 KB	Output is correct
4	Correct	3 ms	1200 KB	Output is correct
5	Correct	4 ms	1200 KB	Output is correct
6	Correct	3 ms	1232 KB	Output is correct
7	Correct	3 ms	1232 KB	Output is correct
8	Correct	3 ms	1232 KB	Output is correct
9	Correct	3 ms	1232 KB	Output is correct
10	Correct	3 ms	1232 KB	Output is correct
11	Correct	3 ms	1232 KB	Output is correct
12	Correct	3 ms	1344 KB	Output is correct
13	Correct	3 ms	1344 KB	Output is correct
14	Correct	3 ms	1344 KB	Output is correct
15	Correct	3 ms	1344 KB	Output is correct
16	Correct	2 ms	1344 KB	Output is correct
17	Correct	2 ms	1344 KB	Output is correct
18	Correct	2 ms	1344 KB	Output is correct
19	Correct	2 ms	1344 KB	Output is correct
20	Correct	3 ms	1344 KB	Output is correct
21	Correct	350 ms	1344 KB	Output is correct
22	Correct	358 ms	1344 KB	Output is correct
23	Correct	330 ms	1344 KB	Output is correct
24	Correct	363 ms	1344 KB	Output is correct
25	Correct	376 ms	1344 KB	Output is correct
26	Correct	389 ms	1344 KB	Output is correct
27	Correct	387 ms	1344 KB	Output is correct
28	Correct	384 ms	1344 KB	Output is correct
29	Correct	391 ms	1344 KB	Output is correct
30	Correct	510 ms	62588 KB	Output is correct
31	Correct	482 ms	62588 KB	Output is correct
32	Correct	494 ms	62604 KB	Output is correct
33	Correct	499 ms	62604 KB	Output is correct
34	Correct	522 ms	62604 KB	Output is correct
35	Correct	476 ms	62604 KB	Output is correct
36	Correct	497 ms	62604 KB	Output is correct
37	Correct	483 ms	62604 KB	Output is correct
38	Correct	529 ms	62604 KB	Output is correct
39	Execution timed out	2085 ms	251756 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

답안 #48375

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