Submission #96477

#	Time	Username	Problem	Language	Result	Execution time	Memory
96477		updown1	Port Facility (JOI17_port_facility)	C++17	78 / 100	6153 ms	970012 KiB

port_facility

/*
https://translate.google.com/translate?sl=auto&tl=en&u=https%3A%2F%2Fwww.ioi-jp.org%2Fcamp%2F2017%2F2017-sp-tasks%2F2017-sp-d1-port_facility-review.pdf
*/
#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, color[MAXN], indst[4*MAXN+1], indend[4*MAXN+1];
pair<int, int> onend[MAXN], onst[MAXN];
vector<pair<int, int> > treest[4*MAXN+1], treeend[4*MAXN+1];
bool del[MAXN];
queue<int> next1;

void build (int ind, int L, int R) {
    if (L == R) {
        if (onst[L].a  != MOD) treest[ind].pb(onst[L]);
        if (onend[L].a != MOD) treeend[ind].pb(onend[L]);
        indst[ind] = treest[ind].size()-1;
        indend[ind] = treeend[ind].size()-1;
        return;
    }
    build(ind*2, L, (L+R)/2); build(ind*2+1, (L+R)/2+1, R);
    for (auto i: treest[ind*2]) treest[ind].pb(i);
    for (auto i: treeend[ind*2]) treeend[ind].pb(i);
    for (auto i: treest[ind*2+1]) treest[ind].pb(i);
    for (auto i: treeend[ind*2+1]) treeend[ind].pb(i);
    sort(treest[ind].begin(), treest[ind].end());
    sort(treeend[ind].begin(), treeend[ind].end());
    reverse(treeend[ind].begin(), treeend[ind].end());
    indst[ind] = treest[ind].size()-1;
    indend[ind] = treeend[ind].size()-1;
}
void queryst(int ind, int L, int R, int oL, int oR, int v, int x) {
    if (oR < L || R < oL) return;
    if (oL <= L && R <= oR) {
        while (indst[ind] != -1 && treest[ind][indst[ind]].a > v) {
            int i = treest[ind][indst[ind]].b;
            if (!del[i]) {
                del[i] = true;
                color[i] = x;
                //w<< "set" s i s x<<e;
                next1.push(i);
            }
            else if (color[i] != x) {
                //w<< "bad" s i c x s color[i]<<e;
                w<< 0<<e;
                exit(0);
            }
            indst[ind] --;
        }
        return;
    }
    queryst(ind*2, L, (L+R)/2, oL, oR, v, x); queryst(ind*2+1, (L+R)/2+1, R, oL, oR, v, x);
}
void queryend(int ind, int L, int R, int oL, int oR, int v, int x) {
    if (oR < L || R < oL) return;
    if (oL <= L && R <= oR) {
        while (indend[ind] != -1 && treeend[ind][indend[ind]].a < v) {
            int i = treeend[ind][indend[ind]].b;
            if (!del[i]) {
                del[i] = true;
                color[i] = x;
                //w<< "set" s i s x<<e;
                next1.push(i);
            }
            else if (color[i] != x) {
                //w<< "bad" s i c x s color[i]<<e;
                w<< 0<<e;
                exit(0);
            }
            indend[ind] --;
        }
        return;
    }
    queryend(ind*2, L, (L+R)/2, oL, oR, v, x); queryend(ind*2+1, (L+R)/2+1, R, oL, oR, v, x);
}

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];
        onst[inp[i][0]] = mp(inp[i][1], i);  /// tree[st] = end
        onst[inp[i][1]] = mp(MOD, -1);
        onend[inp[i][1]] = mp(inp[i][0], i); /// tree[end] = st
        onend[inp[i][0]] = mp(MOD, -1);
        color[i] = 2;
    }
    build(1, 1, 2*N);
    ffi if (!del[i]) {
        /// bfs
        //w<< "set" s i s 1<<e;
        color[i] = 1;
        out *= 2;
        out %= MOD;
        del[i] = true;
        next1.push(i);
        //w<< "going at" s i+1<<e;
        while (!next1.empty()) {
            int a = next1.front(); next1.pop();
            //w<< "at" s a+1<<e;
            /// guaranteed not deleted, but del[a] = false
            queryst(1, 1, 2*N, inp[a][0], inp[a][1], inp[a][1], 1-color[a]);
            queryend(1, 1, 2*N, inp[a][0], inp[a][1], inp[a][0], 1-color[a]);
        }
    }
    w<< out<<e;
}

Compilation message (stderr)

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

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