Submission #47265

#	Time	Username	Problem	Language	Result	Execution time	Memory
47265		Talant	Boat (APIO16_boat)	C++17	31 / 100	1515 ms	252008 KiB

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 (stderr)

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

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