| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 991299 |
2024-06-01T18:47:08 Z |
wood |
Werewolf (IOI18_werewolf) |
C++17 |
|
1478 ms |
39688 KB |
#include "werewolf.h"
#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
constexpr int N = 1e6;
struct segtree
{
int size = 1; vi mx, mn;
segtree(int n){while(size<=n) size*=2; mx.resize(N,0); mn.resize(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 = (l+r)/2;
if(i<m) upd(i,u,2*x+1,l,m);
else upd(i,u,2*x+2,m,r);
mn[x] = min(mn[2*x+1],mn[2*x+2]);
mx[x] = max(mx[2*x+1],mx[2*x+2]);
}
int get(int l, int r, bool ismx){
return get(l,r,ismx,0,0,size);
}
int get(int l, int r, bool ismx, int x, int lx, int rx){
vi& arr = (ismx) ? mx : mn;
if(rx<=l||lx>=r) return (ismx) ? 0 : INT_MAX;
if(lx>=l&&rx<=r) return arr[x];
int m = (rx+lx)/2;
int o = get(l,r,ismx,2*x+1,lx,m);
int t = get(l,r,ismx,2*x+2,m,rx);
if(ismx) return max(o,t); else return min(o,t);
}
};
vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
vi res(S.size());
vi adj[N];
int inds[N];
segtree sgt(N);
//chain setup
for(int i = 0; i<X.size(); i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vi chain;
for(int i = 0; i<N; i++){
if(adj[i].size()==1){
inds[i]=0; sgt.upd(0,i);
chain.pb(i);
int e = adj[i][0];
int p = i;
while(adj[e].size()!=1){
inds[e]=chain.size(); sgt.upd(chain.size(),e);
chain.pb(e);
for(int x : adj[e]) if(x!=p){
p = e;
e = x;
break;
}
}
inds[e]=chain.size(); sgt.upd(chain.size(),e);
chain.pb(e);
break;
}
}
// binary search the intervals assuming all starting pos are smaller
auto x = [&](){
for (size_t i = 0; i < S.size(); i++)
{
if(inds[S[i]]>inds[E[i]]) continue;
if(S[i]<L[i]||E[i]>R[i]){
res[i] = 0;
continue;
}
//find farthes position that can be travelled as a human;
int l = inds[S[i]], r = inds[E[i]]+1;
while(r-l>1){
int m = (r+l)/2;
if(sgt.get(inds[S[i]],m+1,false)<L[i]) r = m;
else l = m;
}
int p = l;
l = inds[E[i]], r = inds[S[i]]-1;
while(l-r>1){
int m = (r+l)/2;
if(sgt.get(m,inds[E[i]]+1,true)>R[i]) r = m;
else l = m;
}
res[i] = p>=l;
}
};
x();
reverse(chain.begin(),chain.end());
for(int i = 0; i<N; i++){
sgt.upd(i,chain[i]);
inds[chain[i]] = i;
}
x();
return res;
}
#ifndef ONLINE_JUDGE
// namespace {
// int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
// } // namespace
// int main() {
// freopen("input.in", "r", stdin);
// freopen("input.out", "w", stdout);
// int N = read_int();
// int M = read_int();
// int Q = read_int();
// std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
// for (int j = 0; j < M; ++j) {
// X[j] = read_int();
// Y[j] = read_int();
// }
// for (int i = 0; i < Q; ++i) {
// S[i] = read_int();
// E[i] = read_int();
// L[i] = read_int();
// R[i] = read_int();
// }
// std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
// for (size_t i = 0; i < A.size(); ++i) {
// printf("%d ", A[i]);
// }
// return 0;
// }
#endif
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i<X.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1363 ms |
31180 KB |
Output is correct |
| 2 |
Correct |
1425 ms |
39628 KB |
Output is correct |
| 3 |
Correct |
1403 ms |
39680 KB |
Output is correct |
| 4 |
Correct |
1366 ms |
39548 KB |
Output is correct |
| 5 |
Correct |
1418 ms |
39628 KB |
Output is correct |
| 6 |
Correct |
1382 ms |
39684 KB |
Output is correct |
| 7 |
Correct |
1421 ms |
39628 KB |
Output is correct |
| 8 |
Correct |
1459 ms |
39628 KB |
Output is correct |
| 9 |
Correct |
581 ms |
39552 KB |
Output is correct |
| 10 |
Correct |
772 ms |
39556 KB |
Output is correct |
| 11 |
Correct |
921 ms |
39688 KB |
Output is correct |
| 12 |
Correct |
957 ms |
39632 KB |
Output is correct |
| 13 |
Correct |
1425 ms |
39548 KB |
Output is correct |
| 14 |
Correct |
1396 ms |
39560 KB |
Output is correct |
| 15 |
Correct |
1402 ms |
39680 KB |
Output is correct |
| 16 |
Correct |
1478 ms |
39560 KB |
Output is correct |
| 17 |
Correct |
1397 ms |
39628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
