제출 #48375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48375		temurbek_khujaev	Boat (APIO16_boat)	C++17	31 / 100	2085 ms	251756 KiB

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42