제출 #42681

#제출 시각아이디문제언어결과실행 시간메모리
42681despasitoAliens (IOI16_aliens)C++14
0 / 100
5 ms5344 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #include <ext/pb_ds/tag_and_trait.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // gives the number of keys with value strictly less than x #define lesscount(x) order_of_key(x) // gives the iterator to kth element (starting from 0) #define kthiterator(x) find_by_order(x) #define clock_starts() clock_t begin = clock() #define clock_ends() clock_t end = clock() #define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \ printf("Elapsed Time : %.10f second(s)\n", elapsed_secs) #define readfile(s) freopen(s, "r", stdin) #define writefile(s) freopen(s, "w", stdout) #define debug(s) cout<< #s <<" = "<< s <<endl #define all(v) (v).begin(), (v).end() #define KeepUnique(v) (v).erase( unique(all(v)), v.end() ) #define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL) #define PrintBinary(n) cout << #n << " = " << bitset<64>(n) << endl #define MEMSET(a,val) memset(a, val, sizeof a) #define PB push_back #define endl '\n' #define cin(n) scanf("%d", &n) #define popcount(x) __builtin_popcount((x)) #define popcountll(x) __builtin_popcountll((x)) inline int myrand(int l, int r) { int ret = rand(); ret <<= 15; ret ^= rand(); if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l; return ret; } template <typename F, typename S> ostream& operator << (ostream& os, const pair< F, S>& p) { return os<<"(" <<p.first<<", "<<p.second<<")"; } typedef pair<int, int> ii; template<typename T> using min_pq = priority_queue<T, vector<T>, greater<T> >; template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); } template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); } template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); } template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); } //int dx[] = {-1, +0, +1, +0}; //int dy[] = {+0, +1, +0, -1}; template<typename T> inline T ceil(T num, T d) { return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); } #define block_no(idx) (idx/BLOCK_SIZE) #define block_starting(idx) (block_no(idx)*BLOCK_SIZE) #define block_ending(idx) (min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1)) #define block_rank(idx) (idx%BLOCK_SIZE) typedef long long ll; const ll is_query = LLONG_MIN+1LL; struct Line { ll m, b; mutable function<const Line*()> succ; bool operator<(const Line& rhs) const { if (rhs.b != is_query) return m < rhs.m; const Line* s = succ(); if (!s) return 0; ll x = rhs.m; return b - s->b < (s->m - m) * x; } }; struct HullDynamic : public multiset<Line> { bool bad(iterator y) { auto z = next(y); if (y == begin()) { if (z == end()) return 0; return y->m == z->m && y->b <= z->b; } auto x = prev(y); if (z == end()) return y->m == x->m && y->b <= x->b; return 1.0*(x->b - y->b)*(z->m - y->m) >= 1.0*(y->b - z->b)*(y->m - x->m); } void addline(ll m, ll b) { auto y = insert({ -m, -b }); y->succ = [=] { return next(y) == end() ? 0 : &*next(y); }; if (bad(y)) { erase(y); return; } while (next(y) != end() && bad(next(y))) erase(next(y)); while (y != begin() && bad(prev(y))) erase(prev(y)); } ll query(ll x) { auto l = *lower_bound((Line) { x, is_query }); return -(l.m * x + l.b); } }; vector<int> L, R; vector<ii> All; int n, m, k; map<ii, int> same; vector<vector<ll> > dp; HullDynamic cht[50010]; inline ll sq(ll x) { return x * x; } long long take_photos(int32_t N, int32_t M, int32_t K, vector<int32_t> RR, vector<int32_t> CC) { n = N, m = M, k = K; for(int i=0; i<n; i++) { int x, y; tie(x, y) = ii(RR[i], CC[i]); if(x > y) swap(x, y); if(same.find(ii(x,y)) == same.end()) same[ii(x,y)], All.push_back(ii(x,y)); } sort(all(All)); { vector<int> tick; tick.assign(All.size(), 1); typedef tuple<int, int, int> trio; vector<tuple<int, int, int> > temp; for(int i=0; i<All.size(); i++) { ii b = All[i]; temp.push_back(trio(b.first, +1, -i)); temp.push_back(trio(b.second, -1, -i)); } sort(all(temp)); int c = 0; for(trio b : temp) { int x, op, id; tie(x, op, id) = b; if(op == -1) { c--; if(c) tick[-id] = 0; } else c++; } for(int i=0; i<All.size(); i++) { if(tick[i]) { L.push_back(All[i].first); R.push_back(All[i].second); } } } n = L.size(); k = min(n, k); dp.assign(k+3, {}); dp[1].assign(n+3, 0); for(int i=0; i<n; i++) { dp[1][i] = (R[i]-L[0]+1)*(R[i]-L[0]+1); } for(int i=2; i<=k; i++) { dp[i].assign(n+3, 0); dp[i][0] = (R[0]-L[0]+1)*(R[0]-L[0]+1); for(int j=1; j<n; j++) { cht[i].addline(-2*L[j], dp[i-1][j-1]+sq(L[j])+sq(max(0, R[j-1]-L[j]+1))); dp[i][j] = sq(R[j]+1) + cht[i].query(R[j]+1); } dp[i-1].clear(); } return dp[k][n-1]; }

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

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<All.size(); i++) {
                 ^
aliens.cpp:147:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<All.size(); i++) {
                 ^
#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...