#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
static struct IO {
char REC; bool REMC = false;
inline void ignore(); inline void flush();
template <typename T> inline bool RIN(T &x); template <typename T> inline bool RST(T &x);
template<size_t N> inline bool RCHA(char (&x)[N]); template<size_t N> inline bool RVR(char (&x)[N]);
template <typename T> inline bool RCH(T &x); inline bool RCHA(char*& x); inline bool RGL(string &x);
template <typename T> inline bool RFL(T &x); template <typename T> inline bool RDB(T &x);
template<size_t N> inline bool RBT(bitset<N> &bit); template<size_t N> inline bool RVR(bitset<N> &bit);
inline bool RVR(bool &x); inline bool RVR(short int &x); inline bool RVR(int &x);
inline bool RVR(long int &x); inline bool RVR(long long int &x); inline bool RVR(unsigned short int &x);
inline bool RVR(unsigned int &x); inline bool RVR(unsigned long &x); inline bool RVR(unsigned long long &x);
inline bool RVR(string &x); inline bool RVR(char &x); inline bool RVR(char*& x); inline bool RVR(float &x);
inline bool RVR(double &x); inline bool RVR(long double &x); template <typename T> inline void WINT(T x);
inline void WSTRING(string &x); inline void WCHAR(char x); inline void WCHAR_ARRAY(const char *x);
inline void WFLOAT(float x); template <typename T> inline void WDOUBLE(T x); inline void WVAR(bool x);
inline void WVAR(short int x); inline void WVAR(int x); inline void WVAR(long int x); inline void WVAR(long long int x);
inline void WVAR(unsigned short int x); inline void WVAR(unsigned int x); inline void WVAR(unsigned long x);
inline void WVAR(unsigned long long x); inline void WVAR(char x); inline void WVAR(const char *x);
inline void WVAR(string &x); inline void WVAR(float x); inline void WVAR(double x); inline void WVAR(long double x);
template<size_t N> inline void WVAR(bitset<N> &bit); template<size_t N> inline void WBITSET(bitset<N> &bit);
} __FIO__;
typedef long long ll;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
int dp[MAXN];
int L[MAXN*50], R[MAXN*50], tree[MAXN*50];
int cnt = 0, m = 0, n = 0, root[MAXN*50];
vector<int> pos, arr[MAXN];
int create(int k) {
int ret = cnt++;
tree[ret] = tree[k];
L[ret] = L[k], R[ret] = R[k];
return ret;
}
int qry(int l, int r, int k, int x, int y) {
if (y < l || r < x) return 0;
if (x <= l && r <= y)
return tree[k];
int mi = (l + r) / 2;
return qry(l, mi, L[k], x, y) + qry(mi + 1, r, R[k], x, y);
}
int upd(int l, int r, int k, int x, int v) {
if (r < x || x < l) return k;
int nk = create(k);
if (x <= l && r <= x) {
tree[nk] += v;
return nk;
}
int mi = (l + r) / 2;
L[nk] = upd(l, mi, L[nk], x, v);
R[nk] = upd(mi + 1, r, R[nk], x, v);
tree[nk] = tree[L[nk]] + tree[R[nk]];
return nk;
}
int build(int l, int r) {
int cur = cnt++;
if (l == r)
return cur;
int mi = (l + r) / 2;
L[cur] = build(l, mi);
R[cur] = build(mi + 1, r);
tree[cur] = tree[L[cur]] + tree[R[cur]];
return cur;
}
void init(int n, int a[], int b[]) {
::n = n;
for (int i = 0; i < n; i++)
arr[a[i] - 1].pb(b[i]);
root[n] = build(0, n+1);
for (int i = n - 1; i >= 0; i--) {
root[i] = root[i + 1];
for (int j: arr[i])
root[i] = upd(0, n+1, root[i], j, 1);
}
}
int gt(int x, int y) {
int lo = y, hi = m + 1;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[mi] - 1) >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[mi] - 1))
hi = mi;
else
lo = mi + 1;
}
return lo;
}
int can(int m, int k[]) {
::m = m;
pos = {0};
vector<int> tmp;
for (int i = 0; i < m; i++) {
pos.push_back(k[i]);
tmp.push_back(k[i]);
}
sort(pos.begin(), pos.end());
vector<int> d;
int curCnt = 0;
for (int i = 0; i <= m; i++) {
if (i > 0) {
while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= i)
d.pop_back();
dp[i] = dp[d.back()] + qry(0, n+1, root[pos[d.back()]], 0, pos[i] - 1) + pos[i];
}
curCnt = max(curCnt, dp[i] + qry(0, n+1, root[pos[i]], 0, n));
if (curCnt > n)
return 0;
while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= gt(d.back(), i))
d.pop_back();
d.push_back(i);
}
return 1;
}
inline void IO::ignore() {
if(REMC == true) REMC = false; else REC = getchar();
}
inline void IO::flush() {
fflush(stdout);
}
template <typename T>
inline bool IO::RIN(T &x) {
x = 0; T sig = 1;
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
if(REC == EOF) return REMC = false, false;
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
x *= sig; REMC = true;
return true;
}
template <typename T>
inline bool IO::RST(T &x) {
x = "";
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
while ((REC == '\n' || REC == '\t' || REC == ' ')) REC = getchar();
if(REC == EOF) return REMC = false, false;
while ((REC != '\n' && REC != '\t' && REC != ' ' && REC != EOF)) x += REC, REC = getchar();
REMC = true;
return true;
}
inline bool IO::RGL(string &x) {
x = "";
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
if(REC == EOF) return REMC = false, false;
while ((REC != '\n' && REC != EOF)) x += REC, REC = getchar();
REMC = false;
return true;
}
template <typename T>
inline bool IO::RCH(T &x) {
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
if(REC == EOF) return REMC = false, false;
while ((REC == '\n' || REC == '\t' || REC == ' ')) REC = getchar();
x = REC; REMC = false;
return true;
}
template<size_t N>
inline bool IO::RCHA(char (&x)[N]) {
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
while ((REC == '\n' || REC == '\t' || REC == ' ')) REC = getchar();
if(REC == EOF) return REMC = false, false;
char *ptr = &x[0];
while ((REC != '\n' && REC != '\t' && REC != ' ' && REC != EOF)) *ptr++ = REC, REC = getchar();
*ptr = '\0', REMC = true;
return true;
}
inline bool IO::RCHA(char*& x) {
string y;
if(RST(y) == false)
return false;
x = new char[(int)y.size() + 1];
strcpy(x, y.c_str());
return true;
}
template <typename T>
inline bool IO::RFL(T &x) {
return (scanf("%f", &x) != EOF);
}
template <typename T>
inline bool IO::RDB(T &x) {
double y;
if(scanf("%lf", &y) == EOF) return false;
x = y;
return true;
}
template<size_t N>
inline bool IO::RBT(bitset<N> &x) {
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
while ((REC == '\n' || REC == '\t' || REC == ' ')) REC = getchar();
if(REC == EOF) return REMC = false, false;
int i = 0; REMC = true;
while (REC == '0' || REC == '1') x[i++] = REC - '0', REC = getchar();
return true;
}
inline bool IO::RVR(short int &x) {
return RIN(x);
}
inline bool IO::RVR(int &x) {
return RIN(x);
}
inline bool IO::RVR(long int &x) {
return RIN(x);
}
inline bool IO::RVR(long long int &x) {
return RIN(x);
}
inline bool IO::RVR(unsigned short int &x) {
return RIN(x);
}
inline bool IO::RVR(unsigned int &x) {
return RIN(x);
}
inline bool IO::RVR(unsigned long &x) {
return RIN(x);
}
inline bool IO::RVR(unsigned long long &x) {
return RIN(x);
}
inline bool IO::RVR(string &x) {
return RST(x);
}
inline bool IO::RVR(char &x) {
return RCH(x);
}
template<size_t N>
inline bool IO::RVR(char (&x)[N]) {
return RCHA(x);
}
inline bool IO::RVR(char*& x) {
return RCHA(x);
}
inline bool IO::RVR(float &x) {
return RFL(x);
}
inline bool IO::RVR(double &x) {
return RDB(x);
}
inline bool IO::RVR(long double &x) {
return RDB(x);
}
template<size_t N>
inline bool IO::RVR(bitset<N> &x) {
return RBT(x);
}
template <typename T>
inline void IO::WINT(T x) {
if (x < 0) {putchar('-'); x = -x; }
char writeBuffer[20], *writePtr = writeBuffer;
do {
*writePtr++ = '0' + x % 10;
x /= 10;
}
while (x);
do { putchar(*--writePtr); }
while (writePtr > writeBuffer);
}
inline void IO::WCHAR(char x) {
putchar(x);
}
inline void IO::WCHAR_ARRAY(const char *x) {
while(*x != '\0')
putchar(*x++);
}
inline void IO::WSTRING(string &x) {
for(char c: x)
putchar(c);
}
inline void IO::WFLOAT(float x) {
printf("%f", x);
}
template <typename T>
inline void IO::WDOUBLE(T x) {
printf("%lf", (double)x);
}
template<size_t N>
inline void IO::WBITSET(bitset<N> &x) {
for(int i = (int)x.size() - 1; i >= 0; i--)
putchar(x[i] + 48);
}
inline void IO::WVAR(bool x) {
WINT(x);
}
inline void IO::WVAR(short int x) {
WINT(x);
}
inline void IO::WVAR(int x) {
WINT(x);
}
inline void IO::WVAR(long int x) {
WINT(x);
}
inline void IO::WVAR(long long int x) {
WINT(x);
}
inline void IO::WVAR(unsigned short int x) {
WINT(x);
}
inline void IO::WVAR(unsigned int x) {
WINT(x);
}
inline void IO::WVAR(unsigned long x) {
WINT(x);
}
inline void IO::WVAR(unsigned long long x) {
WINT(x);
}
inline void IO::WVAR(string &x) {
WSTRING(x);
}
inline void IO::WVAR(char x) {
WCHAR(x);
}
inline void IO::WVAR(const char *x) {
WCHAR_ARRAY(x);
}
inline void IO::WVAR(float x) {
WFLOAT(x);
}
inline void IO::WVAR(double x) {
WDOUBLE(x);
}
inline void IO::WVAR(long double x) {
WDOUBLE(x);
}
template<size_t N>
inline void IO::WVAR(bitset<N> &x) {
WBITSET(x);
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
void init(int n, int a[], int b[]) {
^
teams.cpp:31:21: note: shadowed declaration is here
int cnt = 0, m = 0, n = 0, root[MAXN*50];
^
teams.cpp:77:23: error: 'class std::vector<int>' has no member named 'pb'
arr[a[i] - 1].pb(b[i]);
^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:98:23: warning: declaration of 'm' shadows a global declaration [-Wshadow]
int can(int m, int k[]) {
^
teams.cpp:31:14: note: shadowed declaration is here
int cnt = 0, m = 0, n = 0, root[MAXN*50];
^
teams.cpp: In member function 'void IO::ignore()':
teams.cpp:126:52: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(REMC == true) REMC = false; else REC = getchar();
~~~~~~~^~
teams.cpp: In member function 'bool IO::RGL(std::__cxx11::string&)':
teams.cpp:153:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:155:62: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while ((REC != '\n' && REC != EOF)) x += REC, REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RST(T&) [with T = std::__cxx11::basic_string<char>]':
teams.cpp:179:11: required from here
teams.cpp:144:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:145:67: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while ((REC == '\n' || REC == '\t' || REC == ' ')) REC = getchar();
~~~~~~~^~
teams.cpp:147:91: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while ((REC != '\n' && REC != '\t' && REC != ' ' && REC != EOF)) x += REC, REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = short int]':
teams.cpp:206:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:57: warning: conversion to 'short int' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:41: warning: conversion to 'short int' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~~~~~~~^~~~~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp:138:5: warning: conversion to 'short int' from 'int' may alter its value [-Wconversion]
x *= sig; REMC = true;
~~^~~~~~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = int]':
teams.cpp:209:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = long int]':
teams.cpp:212:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = long long int]':
teams.cpp:215:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = short unsigned int]':
teams.cpp:218:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:57: warning: conversion to 'short unsigned int' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:41: warning: conversion to 'short unsigned int' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~~~~~~~^~~~~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp:138:5: warning: conversion to 'short unsigned int' from 'int' may alter its value [-Wconversion]
x *= sig; REMC = true;
~~^~~~~~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = unsigned int]':
teams.cpp:221:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = long unsigned int]':
teams.cpp:224:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RIN(T&) [with T = long long unsigned int]':
teams.cpp:227:15: required from here
teams.cpp:134:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:135:85: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (!isdigit(REC) && REC != EOF) sig = (REC == '-' ? -sig : sig), REC = getchar();
~~~~~~~^~
teams.cpp:137:61: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while (isdigit(REC)) x = x * 10 + REC - '0', REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'bool IO::RCH(T&) [with T = char]':
teams.cpp:233:15: required from here
teams.cpp:161:26: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
if(!REMC) REC = getchar(), REMC = true; else REMC = false;
~~~~~~~^~
teams.cpp:163:67: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
while ((REC == '\n' || REC == '\t' || REC == ' ')) REC = getchar();
~~~~~~~^~
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = bool]':
teams.cpp:291:9: required from here
teams.cpp:257:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
if (x < 0) {putchar('-'); x = -x; }
~~^~~
teams.cpp:260:23: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
*writePtr++ = '0' + x % 10;
~~~~^~~~~~~~
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = short int]':
teams.cpp:294:9: required from here
teams.cpp:257:31: warning: conversion to 'short int' from 'int' may alter its value [-Wconversion]
if (x < 0) {putchar('-'); x = -x; }
~~^~~~
teams.cpp:260:23: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
*writePtr++ = '0' + x % 10;
~~~~^~~~~~~~
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = int]':
teams.cpp:297:9: required from here
teams.cpp:260:23: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = long int]':
teams.cpp:300:9: required from here
teams.cpp:260:23: warning: conversion to 'char' from 'long int' may alter its value [-Wconversion]
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = long long int]':
teams.cpp:303:9: required from here
teams.cpp:260:23: warning: conversion to 'char' from 'long long int' may alter its value [-Wconversion]
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = short unsigned int]':
teams.cpp:306:9: required from here
teams.cpp:257:31: warning: conversion to 'short unsigned int' from 'int' may alter its value [-Wconversion]
if (x < 0) {putchar('-'); x = -x; }
~~^~~~
teams.cpp:260:23: warning: conversion to 'char' from 'int' may alter its value [-Wconversion]
*writePtr++ = '0' + x % 10;
~~~~^~~~~~~~
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = unsigned int]':
teams.cpp:309:9: required from here
teams.cpp:260:23: warning: conversion to 'char' from 'unsigned int' may alter its value [-Wconversion]
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = long unsigned int]':
teams.cpp:312:9: required from here
teams.cpp:260:23: warning: conversion to 'char' from 'long unsigned int' may alter its value [-Wconversion]
teams.cpp: In instantiation of 'void IO::WINT(T) [with T = long long unsigned int]':
teams.cpp:315:9: required from here
teams.cpp:260:23: warning: conversion to 'char' from 'long long unsigned int' may alter its value [-Wconversion]
