Submission #142752

#	Time	Username	Problem	Language	Result	Execution time	Memory
142752		12tqian	Boat (APIO16_boat)	C++14	100 / 100	1328 ms	21440 KiB

boat

#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const ll MOD = 1e9 + 7;
const int MAX = 505;
const int MAXR = 6*MAX;
vector<pair<ll, ll>> bounds;
vector<pair<ll, ll>> ranges;
ll dp[MAXR][MAX];
ll pre[MAXR][MAX];
ll choose[MAXR][MAX];
ll change[MAXR];
vi possible[MAX];

template<class T, int SZ> struct Seg { // SZ should be power of 2
    T ID = 0; // comb(ID,b) must equal b
    T comb(T a, T b) {
        return (a+b)%MOD;
    } // easily change this to min or max

    T seg[2*SZ];
    Seg() { memset(seg,0,sizeof seg); }


    void upd(int p, T value) {  // set value at position p
        seg[p += SZ] = value;
        for (p /= 2; p; p /= 2) seg[p] = comb(seg[2*p],seg[2*p+1]);
    }

    T query(int l, int r) {  // sum on interval [l, r]
        r ++; T lres = ID, rres = ID; // make sure non-commutative operations work
        for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
            if (l&1) lres = comb(lres,seg[l++]);
            if (r&1) rres = comb(seg[--r],rres);
        }
        return comb(lres,rres);
    }
};
Seg<ll, (1<<13)> seg;



long long modInverse(long long b){
    long long ex = MOD - 2;
    if (b==1){
        return 1;
    }
    long long r = 1;
    while (ex ){
        if (ex&1){
            r=(r * b)%MOD;
        }
        ex = ex >> 1;
        b = (b * b)%MOD;
    }
    return r;
}

int main(){
    fast_io();
    int n;
    scanf("%d", &n);
   // cin >> n;
    map<int, pii> um;
    f0r(i, n){
        int ai, bi;
        scanf("%d %d", &ai, &bi);
        bounds.eb(mp(ai, bi));
        um[ai].f++;
        um[bi].s++;
    }
    vector<pair<int, pii>> v;
    for(auto x: um) v.eb(x);
    vi used;
    f0r(i, sz(v)) used.eb(0);
    f0r(i, sz(v) - 1){
        if(used[i] && used[i+1]){
            int l = v[i].f;
            int r = v[i+1].f;
            if(r-l>1) ranges.eb(mp(l+1, r-1));
        }
        else if(used[i]){
            if(v[i+1].s.f == 0){
                used[i+1] = 1;
                int l = v[i].f;
                int r = v[i+1].f;
                ranges.eb(mp(l+1, r));
            }
            else{
                int l = v[i].f;
                int r = v[i+1].f;
                if(r-l>1) ranges.eb(mp(l+1, r-1));
            }
        }
        else if(used[i+1]){
            if(v[i].s.s == 0){
                used[i] = 1;
                int l = v[i].f;
                int r = v[i+1].f;
                ranges.eb(mp(l, r-1));
            }
            else{
                int l = v[i].f;
                int r = v[i+1].f;
                if(r-l>1) ranges.eb(mp(l+1, r-1));
            }
        }
        else{
            if(v[i].s.s == 0 && v[i+1].s.f == 0){
                used[i] = 1;
                used[i+1] = 1;
                int l = v[i].f;
                int r = v[i+1].f;
                ranges.eb(mp(l, r));
            }
            else{
                int l = v[i].f;
                int r = v[i+1].f;
                if(r-l>1) ranges.eb(mp(l+1, r-1));
            }
        }
    }
    f0r(i,sz(v)){
        if(used[i] == 0){
            ranges.eb(mp(v[i].f, v[i].f));
        }
    }
    sort(all(ranges));
    //for(auto x: ranges) cout << x.f << " " << x.s << endl;
    /*  sort(all(v));
    f0r(i, sz(v) - 1){
        if(v[i] == v[i+1]) continue;
        ranges.eb(mp(v[i], v[i+1] - 1));
    }
    ranges.eb(mp(v[sz(v)-1], v[sz(v) - 1]))*/
    /*
    vi tmp;
    for(auto x: nums) tmp.eb(x);

    f0r(i, sz(tmp) -1){
        if(tmp[i+1]-tmp[i]>1) ranges.eb(tmp[i]+1, tmp[i+1]-1);
    }
    for(auto x: tmp) ranges.eb(mp(x, x));
    sort(all(ranges));*/
 //  cout << sz(ranges) << endl;
    f0r(i, sz(ranges)){
        f0r(j, MAX){
            if(j == 0){
                choose[i][j] = 1;
            }
            else{
                choose[i][j] = choose[i][j-1];
                choose[i][j] *= (ranges[i].s - ranges[i].f+1 -j+ 1);
                choose[i][j] %= MOD;
                choose[i][j] *= modInverse(j);
                choose[i][j] %= MOD;
            }
        }
    }
    f0r(i, n){
        f0r(j, sz(ranges)){
            if(bounds[i].f<= ranges[j].f && bounds[i].s>= ranges[j].s){
                possible[i].eb(j);
            }
        }
    }

    f0r(i, n){
      //  cout << sz(possible[i]) << endl;
        for(int j: possible[i]){
            for(int t = n; t>= 1; t--){
                if(t == 1){
                    dp[j][1] = (j == 0? 0:seg.query(0, j-1)) + 1;
                    pre[j][1] += dp[j][1];
                    if(pre[j][1] >= MOD) pre[j][1] -= MOD;
                    change[j] += (dp[j][1]*choose[j][1])%MOD;
                    if(change[j] >= MOD) change[j] -= MOD;
                    continue;
                }
                dp[j][t] = pre[j][t-1];
                pre[j][t] += dp[j][t];
                if(pre[j][t]>= MOD) pre[j][t] -= MOD;
                change[j] += (dp[j][t]*choose[j][t])%MOD;
                if(change[j]>=MOD) change[j] -= MOD;
            }

        }
        for(int j: possible[i]){
            seg.upd(j, seg.query(j, j)+  change[j]);
        }
        f0r(j, sz(ranges)){
            change[j] = 0;
        }
    }
    printf("%d\n", seg.query(0, sz(ranges) - 1));
    //cout << seg.query(0, sz(ranges) - 1) << endl;
    return 0;
}

Compilation message (stderr)

boat.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
boat.cpp: In function 'int main()':
boat.cpp:242:48: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%d\n", seg.query(0, sz(ranges) - 1));
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
boat.cpp: In function 'void io(std::__cxx11::string)':
boat.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
boat.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &ai, &bi);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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