Submission #373432

#	Time	Username	Problem	Language	Result	Execution time	Memory
373432		cpp219	Pilot (NOI19_pilot)	C++14	100 / 100	842 ms	68388 KiB

pilot

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 9;
const ll inf = 1e16 + 7;
LL q[N];
ll n,Q,ans[N],lab[N],cur,a[N];
deque<ll> dq;
ll Find(ll u){
    if (lab[u] < 0) return u;
    return lab[u] = Find(lab[u]);
}

void Union(ll p,ll q){
    ll r = Find(p),s = Find(q);
    if (r == s) return;
    cur += lab[r]*lab[s];
    if (lab[r] > lab[s]) swap(r,s);
    lab[r] += lab[s]; lab[s] = r;
}

bool lf(ll x,ll y){
    return a[x] < a[y];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>Q; memset(lab,-1,sizeof(lab));
    for (ll i = 1;i <= n;i++) cin>>a[i],dq.push_back(i); sort(dq.begin(),dq.end(),lf);
    for (ll i = 1;i <= Q;i++) cin>>q[i].fs,q[i].sc = i; sort(q + 1,q + Q + 1);
    for (ll i = 1;i <= Q;i++){
        while(!dq.empty()){
            ll t = dq.front();
            if (a[t] > q[i].fs) break; dq.pop_front();
            cur++;
            if (t != 1&&a[t - 1] <= q[i].fs) Union(t,t - 1);
            if (t != n&&a[t + 1] <= q[i].fs) Union(t,t + 1);
        }
        ans[q[i].sc] = cur;
    }
    for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

pilot.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
pilot.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
pilot.cpp: In function 'int main()':
pilot.cpp:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |     for (ll i = 1;i <= n;i++) cin>>a[i],dq.push_back(i); sort(dq.begin(),dq.end(),lf);
      |     ^~~
pilot.cpp:43:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |     for (ll i = 1;i <= n;i++) cin>>a[i],dq.push_back(i); sort(dq.begin(),dq.end(),lf);
      |                                                          ^~~~
pilot.cpp:44:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   44 |     for (ll i = 1;i <= Q;i++) cin>>q[i].fs,q[i].sc = i; sort(q + 1,q + Q + 1);
      |     ^~~
pilot.cpp:44:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   44 |     for (ll i = 1;i <= Q;i++) cin>>q[i].fs,q[i].sc = i; sort(q + 1,q + Q + 1);
      |                                                         ^~~~
pilot.cpp:48:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |             if (a[t] > q[i].fs) break; dq.pop_front();
      |             ^~
pilot.cpp:48:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |             if (a[t] > q[i].fs) break; dq.pop_front();
      |                                        ^~
pilot.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11