| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 610926 | PiejanVDC | Roller Coaster Railroad (IOI16_railroad) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e5+5;
vector<int>st(8*mxN);
int l,r,val;
vector<int>lazy(8*mxN);
int query(int i, int j, int p) {
if(i > r || j < l)
return 0;
if(i >= l && j <= r)
return st[p]+lazy[p];
int mid = (i+j)/2;
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
lazy[p] = 0;
return query(i, mid, 2*p) + query(mid+1, j, 2*p+1);
}
void update(int i, int j, int p) {
if(i > r || j < l)
return;
if(i >= l && j <= r) {
lazy[p] += val;
return;
}
int mid = (i+j)/2;
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
lazy[p] = 0;
update(i, mid, 2*p);
update(mid+1, j, 2*p+1);
}
long long plan_roller_coaster(vector<int>s, vector<int>t) {
set<int>S;
int n = (int)s.size();
for(auto z : s)
S.insert(z);
for(auto z : t)
S.insert(z);
map<int,int>rev;
auto it = S.begin();
for(int i = 0 ; i < 2*n ; i++, it++)
rev[*it] = i;
for(int i = 0 ; i < n ; i++) {
if(s[i] < t[i]) {
auto ff = S.lower_bound(s[i]);
auto ss = S.lower_bound(t[i]);
ss--;
l = rev[*ff], r = rev[*ss];
val = 1;
update(0, 2*n-1, 1);
} else if(s[i] > t[i]) {
auto ss = S.lower_bound(s[i]);
auto ff = S.lower_bound(t[i]);
ss--;
l = rev[*ff], r = rev[*ss];
val = -1;
update(0, 2*n-1, 1);
}
}
long long ret = 0;
vector<int>in(n,0);
for(int i = 0 ; i < 2*n ; i++) {
l = r = i;
int R = query(0, 2*n-1, 1)
if(R > 1)
ret = 1;
/*R--;
R = abs(R);
while(R--)
adj[i].push_back(i+1), in[i+1]++;
if(i)
adj[i].push_back(i-1), in[i-1]++;*/
}
/*for(int i = 0 ; i < n ; i++)
if((int)adj[i].size() != in[i])
ret = 1;
stack<int>q;
q.push(0);
*/
return ret;
}