| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 983817 | wood | 늑대인간 (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
//the only time I thought this could be solved wihtout segment trees segment tree was the answer fml
constexpr int N = 1e6; //change
struct segtree
{
int mx[N] = {0}, mn[N], size = 1;
segtree(int n){while(size<=n)size*=2; fill(mn,mn+N,INT_MAX);}
void upd(int i, int u){
upd(i,u,0,0,size);
}
void upd(int i, int u, int x, int l, int r){
if(r-l==1){
mx[x] = u;
mn[x] = u;
return;
}
int m = (r+l)/2;
if(i<m) upd(i,u,2*x+1,l,m);
else upd(i,u,2*x+2,m,r);
mx[x] = max(mx[2*x+1],mx[2*x+2]);
mn[x] = min(mn[2*x+1],mn[2*x+2]);
}
int get(int l, int r, bool MX){
return get(l,r,0,0,size,MX);
}
int get(int l, int r, int x, int lx, int rx, bool MX){
int* arr = (MX) ? mx : mn;
if(lx>=r||rx<=l) return (MX) ? 0 : INT_MAX;
else if(lx>=l&&rx<=r) return arr[x];
int m = (rx+lx)/2;
int p = get(l,r,2*x+1,lx,m,MX);
int q = get(l,r,2*x+2,m,rx,MX);
if(MX) return max(p,q);
else return min(p,q);
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
int n = N,m = X.size(),q = S.size();
vi adj[n];
for (size_t i = 0; i < m; i++)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vi arr;
for (size_t i = 0; i < N; i++)
{
if(adj[i].size()==1){
int e = -1,x = i ;
while(arr.size()<N){
arr.pb(x);
for(int p : adj[x]){
if(p!=e){
e = x;
x = p;
break;
}
}
}
break;
}
}
segtree sg(n);
int ind[n];
for (size_t i = 0; i < n; i++)
{
sg.upd(i,arr[i]);
ind[arr[i]] = i;
}
vi res;
for (size_t i = 0; i < q; i++)
{
int from_start;
if(S[i]>R[i]||E[i]<L[i]){
res.pb(0);
continue;
}
int s = ind[S[i]], e = ind[E[i]];
//binary search segtree to get the range from start
//and find the furthest index whose min is smaller than R
if(s>e){
int r = s+1, l = e;
while(r-l>1){
int mid = (r+l)/2;
if(sg.get(mid,s+1,true)<=R[i]) r = mid;
else l = mid;
}
if(arr[r]<L[i]||sg.get(e,l,false)<L[i])
res.pb(0);
else res.pb(1);
}
else{
int l = s+1, r = e;
while(r-l>1){
int mid = (r+l)/2;
if(sg.get(s,mid+1,true)<=R[i]) l = mid;
else r = mid;
}
if(arr[l]<L[i]||sg.get(r,e+1,false)<L[i])
res.pb(0);
else res.pb(1);
}
}
return res;
}
int main()
{
fast_cin();
#ifndef ONLINE_JUDGE
#ifdef _WIN32
freopen("input.in", "r", stdin);
freopen("input.out", "w", stdout);
#endif
#endif
for(int i : check_validity(3,{1,2},{2,0},{0},{2},{1},{2})) cout<<i<<' ';
return 0;
}