제출 #592129

#제출 시각아이디문제언어결과실행 시간메모리
592129yutabiAliens (IOI16_aliens)C++14
0 / 100
1 ms332 KiB
#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].first)); } } 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(); 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; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i=1;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:214:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |         if(R<s.size())
      |            ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...