이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
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;}
}
assert(false);
w<< out<<e;
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |