Submission #856961

#	Time	Username	Problem	Language	Result	Execution time	Memory
856961		onepunchac168	Teams (IOI15_teams)	C++14	0 / 100	451 ms	165992 KiB

teams

//------------------------------------\\
//   ------------------------------   \\
//  |  created by Dinh Manh Hung   |  \\
//  |      tht.onepunchac168       |  \\
//  |     THPT CHUYEN HA TINH      |  \\
//  |      HA TINH, VIET NAM       |  \\
//  |           Siuuu              |  \\
//   ------------------------------   \\
//------------------------------------\\

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

#define            task     ""
#define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define             ldb     long double
#define              pb     push_back
#define              eb     emplace_back
#define              fi     first
#define              se     second
#define           all(x)    begin(x),end(x)
#define       uniquev(v)    v.resize(unique(all(v))-v.begin())
#define       rep(i,a,b)    for (int i=a;i<=b;i++)
#define        cntbit(v)    __builtin_popcountll(v)
#define         gcd(a,b)    __gcd(a,b)
#define         lcm(a,b)    ((1LL*a*b)/__gcd(a,b))
#define          mask(x)    (1LL<<(x))
#define     readbit(x,i)    ((x>>i)&1)
#define             Yes     cout << "Yes"
#define             YES     cout << "YES"
#define              No     cout << "No"
#define              NO     cout << "NO"

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const ll mod=1e9+7;
const char nl = '\n';

inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = (xo<<1) + (xo<<3) + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}

// DEBUG
/*
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
*/

/* END OF TEMPLATE*/

// ================= Solution =================//

/*
void onepunchac168();

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    file(task);
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--)
    {
        onepunchac168();
    }
}

const int N=2e5+5;

void onepunchac168()
{

}
// goodbye see ya

*/
const int N=5e5+5;
int n;
vector <int> vt[N];
int a[N];
int b[N];
int supernode=0;
int ver[N];
struct Node{
    int left,right,val;
    Node()
    {

    }
    Node(int left,int right,int val)
    {
        this->left=left;
        this->right=right;
        this->val=val;
    }
} T[N*25];
int update(int oldnode,int l,int r,int u,int val)
{
    if (l==r)
    {
        supernode++;
        T[supernode]=Node(0,0,val+T[oldnode].val);
        return supernode;
    }
    int mid=(l+r)/2;
    int newnode=++supernode;
    if (mid>=u)
    {
        T[newnode].left=update(T[oldnode].left,l,mid,u,val);
        T[newnode].right=T[oldnode].right;
        T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
    }
    else
    {
        T[newnode].left=T[oldnode].left;
        T[newnode].right=update(T[oldnode].right,mid+1,r,u,val);
        T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
    }
    return newnode;
}
ll query(int oldnode,int l,int r,int u,int v)
{
    if (l>v||r<u)
    {
        return 0;
    }
    if (l>=u&&r<=v)
    {
        return T[oldnode].val;
    }
    return query(T[oldnode].left,l,(l+r)/2,u,v)+query(T[oldnode].right,(l+r)/2+1,r,u,v);
}
void init(int na, int aa[], int ba[]) {
    n=na;
    for (int i=1;i<=n;i++)
    {
        a[i]=aa[i-1];
    }
    for (int i=1;i<=n;i++)
    {
        b[i]=ba[i-1];
    }
    for (int i=1;i<=n;i++)
    {
        vt[a[i]].pb(b[i]);
    }
    ver[0]=0;
    T[0]=Node(0,0,0);
    for (int i=1;i<=n;i++)
    {
        ver[i]=ver[i-1];
        for (auto v:vt[i])
        {
            ver[i]=update(ver[i],1,n,v,1);
        }
    }
}
int pp[N];
int can(int m, int ka[]) {
	for (int i=1;i<=m;i++)
    {
        pp[i]=ka[i-1];
    }
    sort (pp+1,pp+m+1);
    ll cnt=0;
    for (int i=1;i<=m;i++)
    {
        if (i==1)
        {

        }
        else if (pp[i]==pp[i-1])
        {

        }
        else
        {
            cnt=max(0LL,cnt-query(ver[pp[i-1]],1,n,pp[i-1],pp[i]-1));
        }
        ll gg=query(ver[pp[i]],1,n,pp[i],n);
        if (gg>=cnt+i)
        {
            cnt+=i;
        }
        else return 0;
    }
    return 1;
}

Compilation message (stderr)

teams.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\\
      | ^
teams.cpp: In function 'int ReadInt()':
teams.cpp:52:22: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   52 |     for (co = getchar(); co < '0' || co > '9'; co = getchar());
      |               ~~~~~~~^~
teams.cpp:52:60: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   52 |     for (co = getchar(); co < '0' || co > '9'; co = getchar());
      |                                                     ~~~~~~~^~
teams.cpp:54:22: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   54 |     for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
      |               ~~~~~~~^~
teams.cpp:54:62: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   54 |     for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
      |                                                       ~~~~~~~^~
teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:141:33: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |                             ~~~~^~~
teams.cpp:136:20: note: shadowed declaration is here
  136 |     int left,right,val;
      |                    ^~~
teams.cpp:141:23: warning: declaration of 'right' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |                   ~~~~^~~~~
teams.cpp:136:14: note: shadowed declaration is here
  136 |     int left,right,val;
      |              ^~~~~
teams.cpp:141:14: warning: declaration of 'left' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |          ~~~~^~~~
teams.cpp:136:9: note: shadowed declaration is here
  136 |     int left,right,val;
      |         ^~~~
teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:141:33: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |                             ~~~~^~~
teams.cpp:136:20: note: shadowed declaration is here
  136 |     int left,right,val;
      |                    ^~~
teams.cpp:141:23: warning: declaration of 'right' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |                   ~~~~^~~~~
teams.cpp:136:14: note: shadowed declaration is here
  136 |     int left,right,val;
      |              ^~~~~
teams.cpp:141:14: warning: declaration of 'left' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |          ~~~~^~~~
teams.cpp:136:9: note: shadowed declaration is here
  136 |     int left,right,val;
      |         ^~~~
teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:141:33: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |                             ~~~~^~~
teams.cpp:136:20: note: shadowed declaration is here
  136 |     int left,right,val;
      |                    ^~~
teams.cpp:141:23: warning: declaration of 'right' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |                   ~~~~^~~~~
teams.cpp:136:14: note: shadowed declaration is here
  136 |     int left,right,val;
      |              ^~~~~
teams.cpp:141:14: warning: declaration of 'left' shadows a member of 'Node' [-Wshadow]
  141 |     Node(int left,int right,int val)
      |          ~~~~^~~~
teams.cpp:136:9: note: shadowed declaration is here
  136 |     int left,right,val;
      |         ^~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23