답안 #878005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878005	2023-11-24T02:04:41 Z	marvinthang	Boat (APIO16_boat)	C++17	31 / 100	1338 ms	524288 KB

boat

/*************************************
*    author: marvinthang             *
*    created: 24.11.2023 08:47:39    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

const int MOD = 1e9 + 7;
namespace MODULAR {
    inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
        unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
    #ifdef __GNUC__
        asm(
            "divl %4 \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (y)
        );
    #else
        __asm {
            mov edx, dword ptr[xh];
            mov eax, dword ptr[xl];
            div dword ptr[y];
            mov dword ptr[d], eax;
            mov dword ptr[m], edx;
        };
    #endif
        out_d = d; out_m = m;
    }
    template <class T> T invGeneral(T a, T b) {
        a %= b;
        if (!a) return b == 1 ? 0 : -1;
        T x = invGeneral(b, a);
        return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
    }
    template <int MOD> struct ModInt {
        unsigned int val;
        ModInt(void): val(0) {}
        ModInt(const long long &x) { *this = x; }
        ModInt & normalize(const unsigned int &v) {
            val = v >= MOD ? v - MOD : v;
            return *this;
        }
        bool operator ! (void) { return !val; }
        ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
        ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }
        ModInt operator - (void) { return ModInt(MOD - val); }
        ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
        ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
        ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }
        ModInt & operator *= (const ModInt &other) {
            unsigned dummy;
            fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
            return *this;
        }
        ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
        ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
        ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
        ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }
        ModInt pow(long long n) const {
            assert(n >= 0);
            ModInt res = 1, a = *this;
            for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
            return res;
        }
        ModInt inv(void) const {
            int i = invGeneral((int) val, MOD);
            assert(~i);
            return i;
        }
        ModInt & operator ++ (void) { return *this += 1; }
        ModInt & operator -- (void) { return *this -= 1; }
        ModInt operator ++ (int) { ModInt old = *this; operator ++(); return old; }
        ModInt operator -- (int) { ModInt old = *this; operator --(); return old; }
        friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
        friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
        friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
        friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
        friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
        friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }
        explicit operator bool(void) const { return val; }
        explicit operator int(void) const { return val; }
    };  
    using Modular = ModInt <MOD>;
}
using namespace MODULAR;

// end of template

struct Node {
	int left, right;
	Modular sum = 0;
	Node *left_child = nullptr, *right_child = nullptr;
	Node(int l, int r): left(l), right(r) {}
	void add(int p, Modular v) {
		sum += v;
		if (right - left == 1) return;
		int mid = (left + right) >> 1;
		if (p < mid) {
			if (left_child == nullptr) left_child = new Node(left, mid);
			left_child->add(p, v);
		} else {
			if (right_child == nullptr) right_child = new Node(mid, right);
			right_child->add(p, v);
		}
	}
	Modular get_sum(int l, int r) {
		if (left >= r || right <= l) return 0;		
		if (l <= left && right <= r) return sum;
		Modular res = 0;
		if (left_child != nullptr) res += left_child->get_sum(l, r);
		if (right_child != nullptr) res += right_child->get_sum(l, r);
		return res;
	}
};

const int INF = 1e9 + 1;

void process(void) {
	int n; cin >> n;
	Node *rt = new Node(0, INF);
	rt->add(0, 1);
	REP(i, n) {
		int a, b; cin >> a >> b;
		FORDE(j, b, a) rt->add(j, rt->get_sum(0, j));
	}
	cout << rt->sum - 1 << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("boat");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:166:2: note: in expansion of macro 'file'
  166 |  file("boat");
      |  ^~~~
boat.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:166:2: note: in expansion of macro 'file'
  166 |  file("boat");
      |  ^~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	1 ms	860 KB	Output is correct
3	Correct	1 ms	860 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	1 ms	860 KB	Output is correct
7	Correct	1 ms	860 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	1 ms	860 KB	Output is correct
12	Correct	1 ms	860 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	1 ms	860 KB	Output is correct
15	Correct	1 ms	860 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	189 ms	920 KB	Output is correct
22	Correct	188 ms	1116 KB	Output is correct
23	Correct	177 ms	928 KB	Output is correct
24	Correct	200 ms	924 KB	Output is correct
25	Correct	198 ms	1108 KB	Output is correct
26	Correct	204 ms	672 KB	Output is correct
27	Correct	210 ms	804 KB	Output is correct
28	Correct	210 ms	776 KB	Output is correct
29	Correct	211 ms	604 KB	Output is correct
30	Correct	251 ms	93264 KB	Output is correct
31	Correct	252 ms	91604 KB	Output is correct
32	Correct	253 ms	93188 KB	Output is correct
33	Correct	253 ms	90784 KB	Output is correct
34	Correct	253 ms	91732 KB	Output is correct
35	Correct	236 ms	87540 KB	Output is correct
36	Correct	253 ms	90832 KB	Output is correct
37	Correct	248 ms	91472 KB	Output is correct
38	Correct	244 ms	88400 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1338 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	1 ms	860 KB	Output is correct
3	Correct	1 ms	860 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	1 ms	860 KB	Output is correct
7	Correct	1 ms	860 KB	Output is correct
8	Correct	1 ms	860 KB	Output is correct
9	Correct	1 ms	860 KB	Output is correct
10	Correct	1 ms	860 KB	Output is correct
11	Correct	1 ms	860 KB	Output is correct
12	Correct	1 ms	860 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	1 ms	860 KB	Output is correct
15	Correct	1 ms	860 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	189 ms	920 KB	Output is correct
22	Correct	188 ms	1116 KB	Output is correct
23	Correct	177 ms	928 KB	Output is correct
24	Correct	200 ms	924 KB	Output is correct
25	Correct	198 ms	1108 KB	Output is correct
26	Correct	204 ms	672 KB	Output is correct
27	Correct	210 ms	804 KB	Output is correct
28	Correct	210 ms	776 KB	Output is correct
29	Correct	211 ms	604 KB	Output is correct
30	Correct	251 ms	93264 KB	Output is correct
31	Correct	252 ms	91604 KB	Output is correct
32	Correct	253 ms	93188 KB	Output is correct
33	Correct	253 ms	90784 KB	Output is correct
34	Correct	253 ms	91732 KB	Output is correct
35	Correct	236 ms	87540 KB	Output is correct
36	Correct	253 ms	90832 KB	Output is correct
37	Correct	248 ms	91472 KB	Output is correct
38	Correct	244 ms	88400 KB	Output is correct
39	Runtime error	1338 ms	524288 KB	Execution killed with signal 9
40	Halted	0 ms	0 KB	-

답안 #878005

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