제출 #1131662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131662		byunjaewoo	Port Facility (JOI17_port_facility)	C++20	0 / 100	114 ms	230348 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

const int N=2000010, S=(1<<21), Mod=1e9+7;
int n, ans=1, l[N], r[N], c[N], il[N], ir[N];
class seg {
public:
    seg() {fill(p+1, p+2*S, -1);}
    void upd(int k, int v) {
        for(k+=S-1; k; k>>=1) tree[k].push_back(v), p[k]=tree[k].size()-1;
    }
    void del(int v) {
        chk[abs(v)]=true;
    }
    int query(int l, int r, int v) {
        for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if(l&1) {
                while(p[l]>=0 && chk[abs(tree[l][p[l]])]) p[l]--;
                if(p[l]>=0 && tree[l][p[l]]>=v) return tree[l][p[l]];
                l++;
            }
            if(!(r&1)) {
                while(p[r]>=0 && chk[abs(tree[r][p[r]])]) p[r]--;
                if(p[r]>=0 && tree[r][p[r]]>=v) return tree[r][p[r]];
                r--;
            }
        }
        if(l==r) {
            while(p[l]>=0 && chk[abs(tree[l][p[l]])]) p[l]--;
            if(p[l]>=0 && tree[l][p[l]]>=v) return tree[l][p[l]];
        }
        return 0;
    }
private:
    vector<int> tree[2*S];
    int p[2*S];
    bool chk[N];
}Tl, Tr;

class seg2 {
public:
    void update(int k, int v) {
        for(k+=S-1; k; k>>=1) tree[k]=max(tree[k], v);
    }
    int query(int l, int r) {
        int ret=0;
        for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if(l&1) ret=max(ret, tree[l++]);
            if(!(r&1)) ret=max(ret, tree[r--]);
        }
        if(l==r) ret=max(ret, tree[l]);
        return ret;
    }
private:
    int tree[2*S];
}T1, T2;

void dfs(int curr) {
    Tl.del(r[curr]), Tr.del(-l[curr]);
    while(true) {
        int next=ir[Tl.query(l[curr], r[curr], r[curr])];
        if(!next) break;
        c[next]=3-c[curr], dfs(next);
    }
    while(true) {
        int next=il[-Tr.query(l[curr], r[curr], -l[curr])];
        if(!next) break;
        c[next]=3-c[curr], dfs(next);
    }
}

signed main() {
    clock_t t1, t2, t3;
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("input.txt", "r", stdin);
    cin>>n;
    vector<pair<int, int>> tmp1, tmp2;
    for(int i=1; i<=n; i++) {
        cin>>l[i]>>r[i], il[l[i]]=i, ir[r[i]]=i;
        tmp1.push_back({r[i], l[i]}), tmp2.push_back({-l[i], r[i]});
    }
    t1=clock();
    sort(tmp1.begin(), tmp1.end()), sort(tmp2.begin(), tmp2.end());
    for(auto [v, k]:tmp1) Tl.upd(k, v);
    for(auto [v, k]:tmp2) Tr.upd(k, v);
    for(int i=1; i<=n; i++) if(!c[i]) {
        c[i]=1, ans=(ans*2)%Mod;
        dfs(i);
    }
    t2=clock();
    for(int i=1; i<=n; i++) {
        if(c[i]==1) T1.update(l[i], r[i]);
        else T2.update(l[i], r[i]);
    }
    for(int i=1; i<=n; i++) {
        if(c[i]==1) {
            if(T1.query(l[i], r[i])>r[i]) {
                cout<<(t2-t1)/CLOCKS_PER_SEC<<"\n";
                cout<<0; return 0;
            }   
        }
        else {
            if(T2.query(l[i], r[i])>r[i]) {
                cout<<(t2-t1)/CLOCKS_PER_SEC<<"\n";
                cout<<0; return 0;
            }
        }
    }
    t3=clock();
    cout<<(double)(t2-t1)/CLOCKS_PER_SEC<<", "<<(double)(t3-t2)/CLOCKS_PER_SEC<<"\n";
    cout<<ans;
    return 0;
}

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

port_facility.cpp: In function 'int main()':
port_facility.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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