QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #769176 | #1096. Best Solution Unknown | XY_Eleven | Compile Error | / | / | C++14 | 6.0kb | 2024-11-21 16:29:30 | 2024-11-21 16:29:31 |
Judging History
answer
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,popcnt,tune=native")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, cnt, cnt2;
int a[N], mx[N][30], mx2[N][30], ans[N], mn[N], mx3[N], q[N], q2[N];
#define FIOBUFSIZ (1<<20|1)
#define NOTONLYDIGIT
#define NEGATIVE
struct freader
{
FILE*f;
# ifdef ONLINE_JUDGE
char buf[FIOBUFSIZ],*p1,*p2;
# define fgetc(f) (p1==p2&&(p2=(p1=buf)+fread(buf,1,FIOBUFSIZ,f),p1==p2)?EOF:*p1++)
# endif
# ifdef BOOLTRANS
bool neof;
# define NEOF(c) ((c)!=EOF||(neof=0))
# else
# define NEOF(c) ((c)!=EOF)
# endif
# ifdef NOTONLYDIGIT
# define isdigit(c) ((c)>='0'&&(c)<='9')
# define isnotdigit(c) ((c)<'0'||(c)>'9')
# else
# define isdigit(c) ((c)>='0')
# define isnotdigit(c) ((c)<'0')
# endif
freader(FILE*_f=stdin):f(_f)
{
# ifdef BOOLTRANS
neof=1;
# endif
# ifdef ONLINE_JUDGE
setvbuf(f,NULL,_IONBF,0);
p1=p2=buf;
# endif
}
# ifdef NOTONLYDIGIT
void read(char&x)
{
for(x=fgetc(f);NEOF(x)&&x<=' ';x=fgetc(f));
return;
}
void read(char*s)
{
for(*s=fgetc(f);NEOF(*s)&&*s<=' ';*s=fgetc(f));
for(s++;NEOF(*s=fgetc(f))&&*s>' ';s++);
*s='\0';
return;
}
freader&operator>>(char*x)
{
# ifdef BOOLTRANS
return *this?read(x),*this:*this;
# else
return read(x),*this;
# endif
}
# endif
template<typename T>void read(T&x)
{
char c(fgetc(f));
# ifdef NEGATIVE
for(;NEOF(c)&&isnotdigit(c)&&c!='-';c=fgetc(f));
if(c=='-')
for(c=fgetc(f),x=0;NEOF(c)&&isdigit(c);c=fgetc(f))
x=(x<<3)+(x<<1)-(c^'0');
else
for(x=0;NEOF(c)&&isdigit(c);c=fgetc(f))
x=(x<<3)+(x<<1)+(c^'0');
# else
for(;NEOF(c)&&isnotdigit(c);c=fgetc(f));
for(x=0;NEOF(c)&&isdigit(c);c=fgetc(f))
x=(x<<3)+(x<<1)+(c^'0');
# endif
return;
}
# if __cplusplus>=201103
template<typename T,typename...Args>void read(T&x,Args&...args){return read(x),read(args...);}
# endif
template<typename T>freader&operator>>(T&x)
{
# ifdef BOOLTRANS
return *this?read(x),*this:*this;
# else
return read(x),*this;
# endif
}
# ifdef BOOLTRANS
operator bool(){return neof;}
# endif
# ifdef ONLINE_JUDGE
# undef fgetc
# endif
# undef NEOF
# undef isdigit
# undef isnotdigit
}fin;
struct fwriter
{
FILE*f;
# ifdef ONLINE_JUDGE
char buf[FIOBUFSIZ],*p1;
# define fputc(c,f) (p1==buf+FIOBUFSIZ?fwrite(buf,1,FIOBUFSIZ,f),*(p1=buf)++=(c):*p1++=(c))
# endif
fwriter(FILE*_f=stdout):f(_f)
{
# ifdef ONLINE_JUDGE
setvbuf(f,NULL,_IONBF,0);
p1=buf;
# endif
}
~fwriter(){flush();}
void flush()
{
# ifdef ONLINE_JUDGE
fwrite(buf,1,p1-buf,f),p1=buf;
# else
fflush(f);
# endif
return;
}
void write(char c)
{
fputc(c,f);
return;
}
void write(char*s)
{
for(;*s;s++)
fputc(*s,f);
return;
}
void write(const char*s)
{
for(;*s;s++)
fputc(*s,f);
return;
}
template<typename T>void write(T x)
{
if(!x)
{
fputc('0',f);
return;
}
if(x<0)
fputc('-',f),x=-x;
char s[41];
int l(0);
while(x)
s[l++]=x%10^'0',x/=10;
while(l--)
fputc(s[l],f);
return;
}
# if __cplusplus>=201103
template<typename T,typename...Args>void write(T x,Args...args){return write(x),write(args...);}
# endif
template<typename T>fwriter&operator<<(T x){return write(x),*this;}
# ifdef ONLINE_JUDGE
# undef fputc
# endif
}fout;
#undef FIOBUFSIZ
int lg[N];
void pre() {
memset(mn, 63, sizeof(mn));
memset(mx3, -63, sizeof(mx3));
for (int i = 1; i <= n; ++i)
mx[i][0] = a[i] + i, mx2[i][0] = a[i] - i;
for (int i = 2; i <= n; ++i)
lg[i] = lg[i >> 1] + 1;
for (int l = 1; l <= lg[n]; ++l) {
for (int i = 1; i + (1 << l) - 1 <= n; ++i) {
int j = i + (1 << l - 1);
mx[i][l] = max(mx[i][l - 1], mx[j][l - 1]);
mx2[i][l] = max(mx2[i][l - 1], mx2[j][l - 1]);
}
}
}
int qmx(int x, int y) {
if (x > y) return -1e9;
int l = lg[y - x + 1];
return max(mx[x][l], mx[y - (1 << l) + 1][l]);
}
int qmx2(int x, int y) {
int l = lg[y - x + 1];
return max(mx2[x][l], mx2[y - (1 << l) + 1][l]);
}
int main () {
// freopen("T1.in", "r", stdin);
// freopen("T1.out", "w", stdout);
// auto it = clock();
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> a[i];
pre();
for (int i = 1; i <= n; ++i) {
int now = a[i];
int pre, pre2;
pre = pre2 = i;
cnt2 = 0;
// cout << i << ":\n";
while (1) {
if (now <= mx3[pre] && now <= mx3[pre2] && (pre != i || pre2 != i)) break;
if (now >= mn[pre] && now >= mn[pre2]) {
pre = 1, pre2 = n;
// putchar('*');
break;
}
// cout << 1;
int l = 1, r = pre - 1, mid, id = 0, f, f2;
f = f2 = 1;
while (l <= r) {
// cout << 2;
mid = (l + r) >> 1;
if (qmx(mid, i - 1) < now + pre)
r = mid - 1, id = mid, f = 0;
else
l = mid + 1;
}
if (!f) {
now += pre - id;
pre = id;
}
// cout << now << ' ' << id << "*\n";
l = pre2 + 1, r = n;
while (l <= r) {
// cout << 3;
mid = (l + r) >> 1;
// cout << mid << ' ' << qmx2(i + 1, mid) << ' ' << now - i << "*\n";
if (qmx2(i + 1, mid) < now - pre2)
l = mid + 1, id = mid, f2 = 0;
else
r = mid - 1;
}
if (!f2) {
now += id - pre2;
pre2 = id;
}
q[++cnt2] = pre, q2[cnt2] = now;
q[++cnt2] = pre2, q2[cnt2] = now;
// cout << pre << ' ' << pre2 << ' ' << now << '\n';
if (f && f2) break;
}
if (pre == 1 && pre2 == n) {
ans[++cnt] = i;
while(cnt2) {
mn[q[cnt2]] = min(mn[q[cnt2]], q2[cnt2]);
cnt2--;
}
}
else {
while(cnt2) {
mx3[q[cnt2]] = max(mx3[q[cnt2]], q2[cnt2]);
cnt2--;
}
}
}
// for (int i = 1; i <= n; ++i)
// cout << mx3[i] << ' ';
fout << cnt << '\n';
for (int i = 1; i < cnt; ++i)
fout << ans[i] << ' ';
fout << ans[cnt];
// cout << clock() - it << "ms\n";
return 0;
}
詳細信息
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
from /usr/include/c++/13/ext/atomicity.h:35,
from /usr/include/c++/13/bits/ios_base.h:39,
from /usr/include/c++/13/streambuf:43,
from /usr/include/c++/13/bits/streambuf_iterator.h:35,
from /usr/include/c++/13/iterator:66,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
from answer.code:3:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...