oj.uz

Submission #1013597

# Submission time Handle Problem Language Result Execution time Memory
1013597 2024-07-03T17:16:50 Z Malix Werewolf (IOI18_werewolf) C++14
34 / 100
 611 ms 524288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vi mins,maxs,arr,p;
int n;

void build(int k,int l,int r){
  if(l==r){
    mins[k]=arr[l];
    maxs[k]=arr[l];
    return;
  }
  int m=(l+r)/2;
  build(k*2,l,m);
  build(k*2+1,m+1,r);
  mins[k]=min(mins[k*2],mins[k*2+1]);
  maxs[k]=max(maxs[k*2],maxs[k*2+1]);
}

int minq(int k,int x,int y,int l,int r){
  if(x>y)return inf;
  if(x==l&&r==y)return mins[k];
  int m=(l+r)/2;
  return min(minq(k*2,x,min(y,m),l,m),minq(k*2+1,max(m+1,x),y,m+1,r));
}

int maxq(int k,int x,int y,int l,int r){//cerr<<x<<" "<<y<<"\n";
  if(x>y)return 0;
  if(x==l&&r==y)return maxs[k];
  int m=(l+r)/2;
  return max(maxq(k*2,x,min(y,m),l,m),maxq(k*2+1,max(m+1,x),y,m+1,r));
}

int BS(int l,int r,int x,int y,int u,int v){//cerr<<l<<" "<<r<<"\n";
  int m=(l+r)/2;
  int a=minq(1,u,m,0,n-1);
  int b=maxq(1,m+1,v,0,n-1);
  int c=arr[m];//cerr<<a<<" "<<b<<" "<<c<<"\n";
  if(x<=c&&c<=y&&a>=x&&b<=y)return 1;
  if(l==r)return 0;
  if(a<x&&b>y)return 0;
  if(a>=x&&b<=y){
    if(c<x)return BS(l,m,x,y,u,v);
    else return BS(m+1,r,x,y,u,v);
  }
  if(a<x)return BS(l,m,x,y,u,v);
  return BS(m+1,r,x,y,u,v);
}

int BS2(int l,int r,int x,int y,int u,int v){//cerr<<l<<" "<<r<<"\n";
  int m=(l+r)/2;
  int a=maxq(1,u,m,0,n-1);
  int b=minq(1,m+1,v,0,n-1);
  int c=arr[m];
  swap(a,b);//cerr<<a<<" "<<b<<" "<<c<<"\n";
  if(x<=c&&c<=y&&a>=x&&b<=y)return 1;
  if(l==r)return 0;
  if(a<x&&b>y)return 0;
  if(a>=x&&b<=y){
    if(c<x)return BS2(m+1,r,x,y,u,v);
    else return BS2(l,m,x,y,u,v);
  }
  if(a<x)return BS2(m+1,r,x,y,u,v);
  return BS2(l,m,x,y,u,v);
}

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) {
  int Q = S.size();
  n=N;
  mins.resize(4*N+1);
  maxs.resize(4*N+1);
  int m=X.size();
  vii a;
  a.resize(N);
  REP(i,0,m){
    a[X[i]].PB(Y[i]);
    a[Y[i]].PB(X[i]);
  }
  int k=0;p.resize(N,-1);
  REP(i,0,N)if(a[i].size()==1)k=i;
  arr.PB(k);
  REP(i,0,N-1){
    int c=a[k][0];
    if(arr.size()>=2&&c==arr[arr.size()-2])c=a[k][1];
    arr.PB(c);
    k=c;
  }
  //reverse(arr.begin(),arr.end());
  REP(i,0,N)p[arr[i]]=i;
  build(1,0,n-1);
  vi ans(Q,0);
  REP(i,0,Q){
    if(p[S[i]]<p[E[i]])ans[i]=BS(p[S[i]],p[E[i]],L[i],R[i],p[S[i]],p[E[i]]);
    else ans[i]=BS2(p[E[i]],p[S[i]],L[i],R[i],p[E[i]],p[S[i]]);
  }
  return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 256 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 256 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 29324 KB Output is correct
2 Correct 267 ms 37828 KB Output is correct
3 Correct 278 ms 37832 KB Output is correct
4 Correct 522 ms 38084 KB Output is correct
5 Correct 611 ms 37760 KB Output is correct
6 Correct 583 ms 37956 KB Output is correct
7 Correct 407 ms 38084 KB Output is correct
8 Correct 285 ms 37828 KB Output is correct
9 Correct 263 ms 38016 KB Output is correct
10 Correct 315 ms 37756 KB Output is correct
11 Correct 521 ms 37948 KB Output is correct
12 Correct 416 ms 37832 KB Output is correct
13 Correct 322 ms 37828 KB Output is correct
14 Correct 329 ms 37744 KB Output is correct
15 Correct 323 ms 37964 KB Output is correct
16 Correct 315 ms 37888 KB Output is correct
17 Correct 454 ms 37828 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 256 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -