QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556150#2299. Heating UpqwqqwqqwqeCompile Error//C++172.9kb2024-09-10 15:23:202024-09-10 15:23:26

Judging History

你现在查看的是最新测评结果

  • [2024-09-10 15:23:26]
  • 评测
查看
  • [2024-09-10 15:23:20]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include"bits/stdc++.h"
#define _det(...) fprintf(stderr,__VA_ARGS__)
#define Print(a) cerr<<a<<"\n"
#define IOS ios::sync_with_stdio(0);cin.tie(0)
#define Cases int T;cin>>T;while(T--)
#define Debug(in) cerr<<#in<<" = "<<(in)<<"\n"
#define Watch(in) Detect;Debug(in);
#define Detect _det("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define ll long long
using namespace std;

const int maxn = 1e6+5;
ll a[maxn];
ll p[maxn];
vector<int> E[maxn];
int n;
int vis[maxn];
int L[maxn]; int R[maxn];

void DFS (int u) {
    for (int v: E[u]) {
        if (vis[v]) continue;
        vis[v] = true; 
        DFS(v);
    }
}

int read () { 
	int x = 0;
	char c = getchar();
	while(c<'0' || c>'9'){
		c = getchar();
	}
	while(c>='0' && c<='9'){
		x = x*10+c-'0';
		c = getchar();
	}
	return x;
}


int check (int mid) {
    //Debug(mid);
    for (int i=1;i<=n+n;i++) E[i].clear();
    for (int i=1;i<=n+n;i++) {
        int to = lower_bound(p+i,p+n+n+1,a[i]+p[i]-mid)-p;
        if (to > i) R[i] = to;
        else R[i] = i;
    }
    for (int i=1;i<=n+n;i++) {
        int to = upper_bound(p+1,p+i+1,p[i-1]+mid-a[i])-p;
        if (to < i) L[i] = to;
        else L[i] = i;
    }
    pair<ll,ll> Rm = {-1e18,1e18}; 
    for (int i=n+n;i>=1;i--) {
        if (R[i] < Rm.second) {
            Rm = {R[i],i};
        }
        if (Rm.first > R[i]) {
            R[i] = Rm.first;
        }
        if (Rm.first <= R[i]) {
            Rm = {R[i],i};
        }
        //Debug(R[i]);
    }
    pair<ll,ll> Lm = {1e18,-1e18}; //mx, from
    for (int i=1;i<=n+n;i++) {
        if (L[i] > Lm.second) {
            Lm = {L[i],i};
        }
        if (Lm.first < L[i]) {
            L[i] = Lm.first;
        }
        if (Lm.first >= L[i]) {
            Lm = {L[i],i};
        }
       // Debug(L[i]);
    }
    for (int i=1;i<=n+n;i++) {
        E[L[i]].push_back(i);
        E[R[i]].push_back(i);
    }
    for (int i=1;i<=n+n;i++) {
        vis[i] = false;
    }
    for (int i=1;i<=n+n;i++) {
        if (a[i] <= mid) {
            vis[i] = true;
            DFS(i);
        }
    }
    for (int i=1;i<=n+n;i++) {
        if (!vis[i]) {
            return false;
        }
    }
    return true;
}

int main () {
    n = read();   
    for (int i=1;i<=n;i++) {
        a[i] = read();
        a[i+n] = a[i];
    }
    for (int i=1;i<=n+n;i++) {
        p[i] = p[i-1]+a[i];
    }
    p[n+n+1] = 1e18;
    ll left = 0;
    ll right = 1e13;
    ll ans = -1;
    while (left<=right) {
        int mid = (left+right)/2;
        if (check(mid)) {
            right = mid-1;
            ans = mid;
        }
        else left = mid+1;
    }
    printf("%lld", ans);
}
Source code, Language: C++17

Details 

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:4:
/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...
English 繁體中文 简体中文

Server Time: 2024-12-02 12:36:37 | OpenSource Project