Submission #1171605

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1171605	2025-03-21 12:48:22	PieArmy	Lightning Conductor (POI11_pio)	C++20	100 / 100	64 ms	21064 KiB

pio

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define int ll
int n;
int arr[500023],pref[500023],ans[500023],spec[500023];
ll kes(int a,int b){
  ll x=arr[a]-arr[b];
  ll y=(a-b-(x*x)-1ll)/ll(2*x);
  return a+max(0ll,min(ll(n-a),y<0?-1ll:(y*y)));
}
void f(){
  for(int i=1;i<=n;i++){
    pref[i]=pref[i-1];
    spec[i]=0;
    if(arr[i]>arr[pref[i]])pref[i]=i;
  }
  int pos=pref[n-1];
  while(pos){
    spec[pos]=1;
    pos=pref[pos-1];
  }
  deque<int>q;
  for(int i=1;i<=n;i++){
    while(q.size()>1){
      if(kes(q[1],q[0])<i)q.pop_front();
      else break;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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