# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
990332 |
2024-05-30T08:26:48 Z |
ian0704 |
Candies (JOI18_candies) |
C++17 |
|
73 ms |
14292 KB |
//try_1 : 구현 이슈로 wa. retry ㄱㄱ
/*# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf=1e18;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
ll arr[200010];
int n;
int ch[200010];
ll sum[200010];
int main()
{
fastio;
cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
sum[1]=arr[1];
for(int i=2;i<=n;i++)
sum[i]=sum[i-2]+arr[i];
priority_queue<pair<ll,pair<ll,ll>>> pq_two;
priority_queue<pair<ll,ll>> pq_one;
set<pair<ll,ll>> s,s2;
for(int i=1;i<=n;i++) pq_one.push({arr[i],i});
ll res=0;
for(int i=1;i<=n/2+n%2;i++)
{
pair<ll,ll> a={-inf,-inf};
while(!pq_one.empty() && ch[pq_one.top().second]) pq_one.pop();
if(!pq_one.empty()) a=pq_one.top();
pair<ll,pair<ll,ll>> b={-inf,{-inf,-inf}};
while(!pq_two.empty() && s2.count(pq_two.top().second)) pq_two.pop();
if(!pq_two.empty()) b=pq_two.top();
ll temp;
cout<<a.first<<" "<<a.second<<" | "<<b.first<<" "<<b.second.first<<" "<<b.second.second<<'\n';
if(a.first>=b.first)
{
res+=a.first;
ch[a.second]=1;
ll l=a.second,r=a.second;
if(l>1) l--;
if(r<n) r++;
auto idx=s.lower_bound({r,0});
if(idx!=s.end())
{
//cout<<"-> "<<(*idx).first<<" "<<(*idx).second<<'\n';
temp=(*idx).first;
if(temp==r)
{
r=(*idx).second;
s2.insert(*idx);
s.erase(idx);
}
}
if(idx!=s.begin())
idx--;
temp=(*idx).second;
if(temp==l)
{
l=(*idx).first;
s2.insert(*idx);
s.erase(idx);
}
s.insert({l,r});
ll num;
if(r==n && r%2!=l%2)
{
num=sum[r-1]-sum[r];
if(l>1) num+=sum[l-1]-sum[l-2];
}
else
{
num=sum[r]-sum[r-1];
if(l>1) num+=sum[l-1]-sum[l-2];
}
pq_two.push({num,{l,r}});
ch[l]=1;
ch[r]=1;
}
else
{
pq_two.pop();
ll l=b.second.first,r=b.second.second;
if(l>1) l--;
if(r<n) r++;
auto idx=s.lower_bound({r,0});
if(idx!=s.end())
{
temp=(*idx).first;
if(temp==r)
{
r=(*idx).second;
s2.insert(*idx);
s.erase(idx);
}
}
if(idx!=s.begin())
idx--;
temp=(*idx).second;
if(temp==l)
{
l=(*idx).first;
s2.insert(*idx);
s.erase(idx);
}
res+=b.first;
s.insert({l,r});
ll num;
if(r==n && l%2!=r%2)
{
num=sum[r-1]-sum[r];
if(l>1) num+=sum[l-1]-sum[l-2];
}
else
{
num=sum[r]-sum[r-1];
if(l>1) num+=sum[l-1]-sum[l-2];
}
pq_two.push({num,{l,r}});
ch[l]=1;
ch[r]=1;
}
cout<<res<<'\n';
}
}*/
//try_2 : 더 간단하게 pq 하나로 구현 ㄱㄱ
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
int n;
const ll inf=1e18;
struct Candy
{
ll num,l,r,ch=0;
};
Candy arr[200010];
priority_queue<pair<ll,ll>> pq;
int main()
{
fastio;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i].num;
pq.push({arr[i].num,i});
arr[i].l=i-1;
arr[i].r=i+1;
}
ll res=0;
arr[0].num=-inf;
arr[n+1].num=-inf;
for(int i=1;i<=n/2+n%2;i++)
{
while(!pq.empty() && arr[pq.top().second].ch) pq.pop();
auto a=pq.top();
pq.pop();
arr[arr[a.second].l].ch=1;
arr[arr[a.second].r].ch=1;
res+=a.first;
arr[a.second].num=arr[arr[a.second].l].num+arr[arr[a.second].r].num-arr[a.second].num;
arr[a.second].l=arr[arr[a.second].l].l;
arr[arr[a.second].l].r=a.second;
arr[a.second].r=arr[arr[a.second].r].r;
arr[arr[a.second].r].l=a.second;
pq.push({arr[a.second].num,a.second});
cout<<res<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
4 |
Correct |
2 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
6804 KB |
Output is correct |
13 |
Correct |
2 ms |
6748 KB |
Output is correct |
14 |
Correct |
2 ms |
6748 KB |
Output is correct |
15 |
Correct |
2 ms |
6748 KB |
Output is correct |
16 |
Correct |
2 ms |
6752 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
2 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6744 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
4 |
Correct |
2 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
6804 KB |
Output is correct |
13 |
Correct |
2 ms |
6748 KB |
Output is correct |
14 |
Correct |
2 ms |
6748 KB |
Output is correct |
15 |
Correct |
2 ms |
6748 KB |
Output is correct |
16 |
Correct |
2 ms |
6752 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
2 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6744 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
21 |
Correct |
71 ms |
12716 KB |
Output is correct |
22 |
Correct |
73 ms |
13264 KB |
Output is correct |
23 |
Correct |
66 ms |
13652 KB |
Output is correct |
24 |
Correct |
54 ms |
13268 KB |
Output is correct |
25 |
Correct |
54 ms |
13520 KB |
Output is correct |
26 |
Correct |
53 ms |
13244 KB |
Output is correct |
27 |
Correct |
62 ms |
13360 KB |
Output is correct |
28 |
Correct |
62 ms |
13248 KB |
Output is correct |
29 |
Correct |
63 ms |
13388 KB |
Output is correct |
30 |
Correct |
67 ms |
14280 KB |
Output is correct |
31 |
Correct |
63 ms |
13412 KB |
Output is correct |
32 |
Correct |
65 ms |
13780 KB |
Output is correct |
33 |
Correct |
67 ms |
13012 KB |
Output is correct |
34 |
Correct |
62 ms |
13008 KB |
Output is correct |
35 |
Correct |
68 ms |
13212 KB |
Output is correct |
36 |
Correct |
66 ms |
13288 KB |
Output is correct |
37 |
Correct |
66 ms |
13248 KB |
Output is correct |
38 |
Correct |
68 ms |
13516 KB |
Output is correct |
39 |
Correct |
55 ms |
13248 KB |
Output is correct |
40 |
Correct |
53 ms |
13248 KB |
Output is correct |
41 |
Correct |
54 ms |
14292 KB |
Output is correct |
42 |
Correct |
62 ms |
13780 KB |
Output is correct |
43 |
Correct |
62 ms |
13540 KB |
Output is correct |
44 |
Correct |
67 ms |
13248 KB |
Output is correct |
45 |
Correct |
62 ms |
13248 KB |
Output is correct |
46 |
Correct |
62 ms |
13320 KB |
Output is correct |
47 |
Correct |
62 ms |
13916 KB |
Output is correct |
48 |
Correct |
63 ms |
13000 KB |
Output is correct |
49 |
Correct |
66 ms |
13520 KB |
Output is correct |
50 |
Correct |
62 ms |
13264 KB |
Output is correct |