# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
592131 | 2022-07-08T15:07:06 Z | yutabi | Aliens (IOI16_aliens) | C++14 | 1 ms | 312 KB |
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; typedef pair <ll,ll> ii; int par[200007]; int r[200007]; int find_parent(int a) { if(par[a]==a) { return a; } return a=find_parent(par[a]); } void make_union(int a, int b) { a=find_parent(a); b=find_parent(b); if(a==b) { return; } if(a>b) { swap(a,b); } par[b]=a; r[a]=r[b]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { int K=n; vector <ii> s; vector <ii> nw; for(int i=0;i<n;i++) { s.pb(ii(r[i],c[i])); } for(int i=0;i<n;i++) { if(s[i].first<s[i].second) { nw.pb(ii(s[i].second,s[i].first)); } else { nw.pb(ii(s[i].first,s[i].second)); } } s=nw; nw.clear(); vector <ll> best(m,m*2); for(int i=0;i<s.size();i++) { best[s[i].first]=min(best[s[i].first],s[i].second); } for(int i=0;i<s.size();i++) { if(best[s[i].first]==s[i].second) { nw.pb(s[i]); best[s[i].first]--; } } s=nw; nw.clear(); sort(s.begin(),s.end()); for(int i=0;i<s.size();i++) { while(nw.size() && s[i].second<=nw.back().second) { nw.pop_back(); } nw.push_back(s[i]); } s=nw; nw.clear(); for(int i=0;i<s.size();i++) { //printf("%d %d\n",s[i].first,s[i].second); } ll ans=1; ans*=s[0].first-s[0].second+1; ans*=s[0].first-s[0].second+1; //printf("%lld\n",ans); priority_queue <pair <ll,ii> > pq; for(int i=0;i<s.size();i++) { par[i]=r[i]=i; } for(int i=1;i<s.size();i++) { ll ee=1; ee*=s[i-1].first-s[i].second+1; ee*=s[i-1].first-s[i].second+1; if(s[i].second>s[i-1].first) { ee=0; } ans-=ee; ans+=(s[i].first-s[i].second+1)*(s[i].first-s[i].second+1); pq.push(make_pair(-(((s[i].first-s[i-1].second+1)*(s[i].first-s[i-1].second+1))-((s[i].first-s[i].second+1)*(s[i].first-s[i].second+1))-((s[i-1].first-s[i-1].second+1)*(s[i-1].first-s[i-1].second+1))+(ee)),ii(i-1,i))); } K=s.size(); //printf("%lld\n",K); while(K>n) { ll val=-pq.top().first; int fr=pq.top().second.first; int sc=pq.top().second.second; pq.pop(); fr=find_parent(fr); sc=find_parent(sc); if(fr==sc) { continue; } ll ee=(s[fr].first-s[sc].second+1)*(s[fr].first-s[sc].second+1); if(s[sc].second>s[fr].first) { ee=0; } ll nw_val=(s[sc].first-s[fr].second+1)*(s[sc].first-s[fr].second+1); nw_val-=(s[fr].first-s[fr].second+1)*(s[fr].first-s[fr].second+1); nw_val-=(s[sc].first-s[sc].second+1)*(s[sc].first-s[sc].second+1); nw_val+=ee; if(nw_val!=val) { continue; } ans+=val; make_union(fr,sc); s[fr].first=s[sc].first; int L=fr-1; int R=r[fr]+1; if(L>=0) { ee=(s[L].first-s[fr].second+1)*(s[L].first-s[fr].second+1); if(s[fr].second>s[L].first) { ee=0; } nw_val=(s[fr].first-s[L].second+1)*(s[fr].first-s[L].second+1); nw_val-=(s[fr].first-s[fr].second+1)*(s[fr].first-s[fr].second+1); nw_val-=(s[L].first-s[L].second+1)*(s[L].first-s[L].second+1); nw_val+=ee; pq.push(make_pair(-nw_val,ii(L,fr))); } if(R<s.size()) { ee=(s[fr].first-s[R].second+1)*(s[fr].first-s[R].second+1); nw_val=(s[R].first-s[fr].second+1)*(s[R].first-s[fr].second+1); nw_val-=(s[fr].first-s[fr].second+1)*(s[fr].first-s[fr].second+1); nw_val-=(s[R].first-s[R].second+1)*(s[R].first-s[R].second+1); nw_val+=ee; pq.push(make_pair(-nw_val,ii(fr,R))); } k--; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
2 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 212 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 212 KB | Correct answer: answer = 12 |
5 | Correct | 1 ms | 212 KB | Correct answer: answer = 52 |
6 | Correct | 1 ms | 212 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 212 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 212 KB | Correct answer: answer = 7696 |
9 | Correct | 1 ms | 212 KB | Correct answer: answer = 1 |
10 | Correct | 1 ms | 212 KB | Correct answer: answer = 2374 |
11 | Correct | 1 ms | 212 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 212 KB | Correct answer: answer = 49 |
13 | Correct | 1 ms | 212 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 212 KB | Correct answer: answer = 7550 |
15 | Correct | 1 ms | 212 KB | Correct answer: answer = 7220 |
16 | Correct | 0 ms | 212 KB | Correct answer: answer = 7550 |
17 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
18 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 212 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 212 KB | Correct answer: answer = 10000 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct answer: answer = 1 |
2 | Incorrect | 0 ms | 212 KB | Wrong answer: output = 2, expected = 4 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
2 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 212 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 212 KB | Correct answer: answer = 12 |
5 | Correct | 1 ms | 212 KB | Correct answer: answer = 52 |
6 | Correct | 1 ms | 212 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 212 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 212 KB | Correct answer: answer = 7696 |
9 | Correct | 1 ms | 212 KB | Correct answer: answer = 1 |
10 | Correct | 1 ms | 212 KB | Correct answer: answer = 2374 |
11 | Correct | 1 ms | 212 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 212 KB | Correct answer: answer = 49 |
13 | Correct | 1 ms | 212 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 212 KB | Correct answer: answer = 7550 |
15 | Correct | 1 ms | 212 KB | Correct answer: answer = 7220 |
16 | Correct | 0 ms | 212 KB | Correct answer: answer = 7550 |
17 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
18 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 212 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 212 KB | Correct answer: answer = 10000 |
21 | Correct | 0 ms | 212 KB | Correct answer: answer = 1 |
22 | Incorrect | 0 ms | 212 KB | Wrong answer: output = 2, expected = 4 |
23 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
2 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 212 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 212 KB | Correct answer: answer = 12 |
5 | Correct | 1 ms | 212 KB | Correct answer: answer = 52 |
6 | Correct | 1 ms | 212 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 212 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 212 KB | Correct answer: answer = 7696 |
9 | Correct | 1 ms | 212 KB | Correct answer: answer = 1 |
10 | Correct | 1 ms | 212 KB | Correct answer: answer = 2374 |
11 | Correct | 1 ms | 212 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 212 KB | Correct answer: answer = 49 |
13 | Correct | 1 ms | 212 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 212 KB | Correct answer: answer = 7550 |
15 | Correct | 1 ms | 212 KB | Correct answer: answer = 7220 |
16 | Correct | 0 ms | 212 KB | Correct answer: answer = 7550 |
17 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
18 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 212 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 212 KB | Correct answer: answer = 10000 |
21 | Correct | 0 ms | 212 KB | Correct answer: answer = 1 |
22 | Incorrect | 0 ms | 212 KB | Wrong answer: output = 2, expected = 4 |
23 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
2 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 212 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 212 KB | Correct answer: answer = 12 |
5 | Correct | 1 ms | 212 KB | Correct answer: answer = 52 |
6 | Correct | 1 ms | 212 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 212 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 212 KB | Correct answer: answer = 7696 |
9 | Correct | 1 ms | 212 KB | Correct answer: answer = 1 |
10 | Correct | 1 ms | 212 KB | Correct answer: answer = 2374 |
11 | Correct | 1 ms | 212 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 212 KB | Correct answer: answer = 49 |
13 | Correct | 1 ms | 212 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 212 KB | Correct answer: answer = 7550 |
15 | Correct | 1 ms | 212 KB | Correct answer: answer = 7220 |
16 | Correct | 0 ms | 212 KB | Correct answer: answer = 7550 |
17 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
18 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 212 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 212 KB | Correct answer: answer = 10000 |
21 | Correct | 0 ms | 212 KB | Correct answer: answer = 1 |
22 | Incorrect | 0 ms | 212 KB | Wrong answer: output = 2, expected = 4 |
23 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
2 | Correct | 0 ms | 212 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 212 KB | Correct answer: answer = 4 |
4 | Correct | 1 ms | 212 KB | Correct answer: answer = 12 |
5 | Correct | 1 ms | 212 KB | Correct answer: answer = 52 |
6 | Correct | 1 ms | 212 KB | Correct answer: answer = 210 |
7 | Correct | 0 ms | 212 KB | Correct answer: answer = 88 |
8 | Correct | 0 ms | 212 KB | Correct answer: answer = 7696 |
9 | Correct | 1 ms | 212 KB | Correct answer: answer = 1 |
10 | Correct | 1 ms | 212 KB | Correct answer: answer = 2374 |
11 | Correct | 1 ms | 212 KB | Correct answer: answer = 9502 |
12 | Correct | 0 ms | 212 KB | Correct answer: answer = 49 |
13 | Correct | 1 ms | 212 KB | Correct answer: answer = 151 |
14 | Correct | 1 ms | 212 KB | Correct answer: answer = 7550 |
15 | Correct | 1 ms | 212 KB | Correct answer: answer = 7220 |
16 | Correct | 0 ms | 212 KB | Correct answer: answer = 7550 |
17 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
18 | Correct | 0 ms | 312 KB | Correct answer: answer = 10000 |
19 | Correct | 0 ms | 212 KB | Correct answer: answer = 624 |
20 | Correct | 1 ms | 212 KB | Correct answer: answer = 10000 |
21 | Correct | 0 ms | 212 KB | Correct answer: answer = 1 |
22 | Incorrect | 0 ms | 212 KB | Wrong answer: output = 2, expected = 4 |
23 | Halted | 0 ms | 0 KB | - |