| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 81517 |
2018-10-25T08:03:47 Z |
zubec |
Werewolf (IOI18_werewolf) |
C++14 |
|
4000 ms |
27836 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
vector <int> g[N];
int a[N], pos[N], t[2][N*4];
void update(int v, int l, int r, int pos, int x){
if (l == r){
t[0][v] = x;
t[1][v] = x;
return;
}
int mid = (l+r)>>1;
if (pos <= mid)
update(v+v, l, mid, pos, x); else
update(v+v+1, mid+1, r, pos, x);
t[0][v] = min(t[0][v+v], t[0][v+v+1]);
t[1][v] = max(t[1][v+v], t[1][v+v+1]);
}
int getMn(int v, int l, int r, int tl, int tr){
if (l > r || tl > r || l > tr || tl > tr)
return 1e9;
if (tl <= l && r <= tr){
return t[0][v];
}
int mid = (l+r)>>1;
return min(getMn(v+v, l, mid, tl, tr), getMn(v+v+1, mid+1, r, tl, tr));
}
int getMx(int v, int l, int r, int tl, int tr){
if (l > r || tl > r || l > tr || tl > tr)
return 0;
if (tl <= l && r <= tr){
return t[1][v];
}
int mid = (l+r)>>1;
return max(getMx(v+v, l, mid, tl, tr), getMx(v+v+1, mid+1, r, tl, tr));
}
int getRMn(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (mid <= pos){
return getRMn(v+v+1, mid+1, r, pos, x);
}
if (t[0][v+v] < x){
return getRMn(v+v, l, mid, pos, x);
}
return getRMn(v+v+1, mid+1, r, pos, x);
}
int getLMn(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (pos <= mid+1)
return getLMn(v+v, l, mid, pos, x);
if (t[0][v+v+1] < x)
return getLMn(v+v+1, mid+1, r, pos, x);
return getLMn(v+v, l, mid, pos, x);
}
int getRMx(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (mid <= pos){
return getRMx(v+v+1, mid+1, r, pos, x);
}
if (t[1][v+v] > x){
return getRMx(v+v, l, mid, pos, x);
}
return getRMx(v+v+1, mid+1, r, pos, x);
}
int getLMx(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (pos <= mid+1)
return getLMx(v+v, l, mid, pos, x);
if (t[1][v+v+1] > x)
return getLMx(v+v+1, mid+1, r, pos, x);
return getLMx(v+v, l, mid, pos, x);
}
std::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) {
for (int i = 0; i < N; i++){
g[i].clear();
}
for (int i = 0; i < X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int cur = 0;
for (int i = 0; i < N; i++){
if (g[i].size() == 1){
cur = i;
break;
}
}
int prev = -1;
for (int i = 0; i < N; i++){
pos[cur] = i;
a[i] = cur;
update(1, 0, N-1, i, cur);
for (int j = 0; j < g[cur].size(); j++){
int to = g[cur][j];
if (to == prev)
continue;
prev = cur;
cur = to;
break;
}
}
vector <int> A;
for (int ii = 0; ii < S.size(); ii++){
int s = S[ii], e = E[ii];
int l = L[ii], r = R[ii];
/*int x1 = getLMn(1, 0, N-1, pos[s], l);
int y1 = getRMn(1, 0, N-1, pos[s], l);
int x2 = getLMx(1, 0, N-1, pos[e], r);
int y2 = getRMx(1, 0, N-1, pos[e], r);
if (a[x1] < l)
++x1;
if (a[y1] < l)
--y1;
if (a[x2] > r)
++x2;
if (a[y2] > r)
--y2;*/
int x1, y1, x2, y2;
int tl = 0, tr = pos[s];
while(tl < tr){
int mid = (tl+tr)>>1;
if (getMn(1, 0, N-1, mid, pos[s]) < l)
tl = mid+1; else
tr = mid;
}
x1 = tl;
tl = pos[s], tr = N-1;
while(tl < tr){
int mid = (tl+tr+1)>>1;
if (getMn(1, 0, N-1, pos[s], mid) < l)
tr = mid-1; else
tl = mid;
}
y1 = tl;
tl = 0, tr = pos[e];
while(tl < tr){
int mid = (tl+tr)>>1;
if (getMx(1, 0, N-1, mid, pos[e]) > r)
tl = mid+1; else
tr = mid;
}
x2 = tl;
tl = pos[e], tr = N-1;
while(tl < tr){
int mid = (tl+tr+1)>>1;
if (getMx(1, 0, N-1, pos[e], mid) > r)
tr = mid-1; else
tl = mid;
}
y2 = tl;
int bb = 0;
//cout << "kek " << x1 << ' ' << y1 << " " << x2 << ' ' << y2 << endl;
int x3 = max(x1, x2);
int y3 = min(y1, y2);
if (x3 <= y3)
bb = 1;
A.push_back(bb);
}
return A;
}
/**
5 4 1
1 0
0 3
3 4
4 2
1 2 0 3
*/
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:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[cur].size(); j++){
~~^~~~~~~~~~~~~~~
werewolf.cpp:126:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ii = 0; ii < S.size(); ii++){
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4030 ms |
27836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
