Submission #96069

#	Time	Username	Problem	Language	Result	Execution time	Memory
96069		updown1	Port Facility (JOI17_port_facility)	C++17	0 / 100	2 ms	376 KiB

port_facility

/*
tree[end index] = pair<smallest start index, 2nd smallest start index>
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, P)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//500,000,000 operations
const int MAXN = 2000001, MOD = 1000000007;
//Global Variables
int N, inp[MAXN][2], out = 1, on[MAXN];
pair<int, int> tree[4*MAXN+1];

void build (int ind, int L, int R) {
    if (L == R) {
        tree[ind] = mp(on[L], MOD);
        return;
    }
    build(ind*2, L, (L+R)/2); build(ind*2+1, (L+R)/2+1, R);
    int use[] = {tree[ind*2].a, tree[ind*2].b, tree[ind*2+1].a, tree[ind*2+1].b};
    sort(use, use+4);
    tree[ind] = mp(use[0], use[1]);
}
pair<int, int> query(int ind, int L, int R, int oL, int oR) {
    if (oL <= L && R <= oR) return tree[ind];
    if (R < oL || oR < L) return mp(MOD, MOD);
    pair<int, int> a = query(ind*2, L, (L+R)/2, oL, oR);
    pair<int, int> b = query(ind*2+1, (L+R)/2+1, R, oL, oR);
    int use[] = {a.a, a.b, b.a, b.b};
    sort(use, use+4);
    return mp(use[0], use[1]);
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    //For (i, 0, MAXN) tree[i] = mp(MOD, MOD);
    ffi {
        cin >> inp[i][0] >> inp[i][1];
        on[inp[i][1]] = inp[i][0];
        on[inp[i][0]] = MOD;
    }
    build(1, 1, 2*N);
    ffi {
        pair<int, int> got = query(1, 1, 2*N, inp[i][0], inp[i][1]);
        //w<< i c got.a s got.b<<e;
        if (got.b < inp[i][0]) {w<< 0<<e; return 0;}
        if (got.a >= inp[i][0]) {out *= 2; out %= MOD;}
    }
    w<< out<<e;
}

Compilation message (stderr)

port_facility.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22