Submission #877790

#	Time	Username	Problem	Language	Result	Execution time	Memory
877790		8pete8	Werewolf (IOI18_werewolf)	C++14	100 / 100	1308 ms	310888 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>  
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define ll long long    
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#pragma GCC optimize ("03,unroll-lopps")
#pragma GCC target("avx2")
const int mxn=7e5,lg=35;
struct kst{
  int pa[mxn+10],cnt=0,val[mxn+10],up[mxn+10][lg+5];
  pii mnmx[mxn+10];
  vector<int>adj[mxn+10],pos;
  void init(){for(int i=0;i<=mxn;i++)pa[i]=i;}
  int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
  void merg(int a,int b){
    cnt++;
    int u=find(a),v=find(b);
    adj[cnt].pb(u);
    pa[u]=cnt;
    if(u==v)return;
    adj[cnt].pb(v);
    pa[v]=cnt;
  }
  void dfs(int cur,int n){
    for(auto i:adj[cur])up[i][0]=cur,dfs(i,n);
    if(cur<n)pos.pb(cur);
  }
  void dfs2(int cur){for(auto i:adj[cur])dfs2(i),mnmx[cur]={min(mnmx[cur].f,mnmx[i].f),max(mnmx[cur].s,mnmx[i].s)};}
  void upd(vector<ppii>e,int n){
    cnt=n-1;
    for(auto i:e)merg(i.s.f,i.s.s),val[cnt]=i.f;
    for(int i=0;i<n;i++)val[i]=i;
    dfs(cnt,n);
    for(int i=0;i<n;i++)mnmx[pos[i]]={i,i};
    for(int i=n;i<=cnt;i++)mnmx[i]={1e9,-1e9};
    for(int i=0;i<=lg;i++)up[cnt][i]=cnt;
    for(int j=1;j<=lg;j++)for(int i=0;i<=cnt;i++)up[i][j]=up[up[i][j-1]][j-1];
    dfs2(cnt);
  }
}k[2];
struct fen{
  int bit[mxn+10];
  void update(int pos,int n){for(int i=pos;i<=n;i+=(i&-i))bit[i]++;}
  int qry(int pos){
    int sum=0;
    for(int i=pos;i>0;i-=(i&-i))sum+=bit[i];
    return sum;
  }
}f;
vector<int> check_validity(int n,vector<int>x,vector<int>y,vector<int>st,vector<int>e,vector<int>l,vector<int>r){
  vector<ppii>g;
  for(int i=0;i<x.size();i++)g.pb({min(x[i],y[i]),{x[i],y[i]}});
  sort(rall(g));
  k[0].init();
  k[0].upd(g,n);
  g.clear();
  for(int i=0;i<x.size();i++)g.pb({max(x[i],y[i]),{x[i],y[i]}});
  sort(all(g));
  k[1].init();
  k[1].upd(g,n);
  int cur,cur2;
  vector<pair<pii,pii>>qry;
  for(int i=0;i<st.size();i++){
    cur=st[i];
    for(int j=lg;j>=0;j--)if(k[0].val[k[0].up[cur][j]]>=l[i])cur=k[0].up[cur][j];
    cur2=e[i];
    for(int j=lg;j>=0;j--)if(k[1].val[k[1].up[cur2][j]]<=r[i])cur2=k[1].up[cur2][j];
    qry.pb({{k[0].mnmx[cur].f-1,i+1},k[1].mnmx[cur2]});
    qry.pb({{k[0].mnmx[cur].s,-(i+1)},k[1].mnmx[cur2]});
  }
  vector<int>ans(st.size());
  sort(all(qry));
  int id,mul=1;
  cur=0;
  for(int i=0;i<qry.size();i++){
    if(qry[i].f.s>0)id=qry[i].f.s-1,mul=-1;
    else id=-(qry[i].f.s)-1,mul=1;
    while(cur<=qry[i].f.f)f.update(k[1].mnmx[k[0].pos[cur]].f+1,n),cur++;
    ans[id]+=((f.qry(qry[i].s.s+1)*mul)-(f.qry(qry[i].s.f)*mul));
  }
  for(auto &i:ans)i=!!i;
  return ans;
  /*
  range l1,r2 l2,r2
  find how many on from 1->l2-1,and 1->r2
  find on 1->x; for qry i;
  foreach qry l1,r1; sort(all) l1,r1
  to get x when l1,r1 is on is (1->x when r1)-(1->x when l1-1);
  */
}

Compilation message (stderr)

werewolf.cpp:30:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   31 | #pragma GCC target("avx2")
      |                          ^
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
werewolf.cpp:31:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51