제출 #821916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821916		bane	Aliens (IOI16_aliens)	C++17	4 / 100	2 ms	2004 KiB

aliens

        #include <iostream>
        #include <cstdio>
        #include <cstdlib>
        #include <algorithm>
        #include <cmath>
        #include <vector>
        #include <set>
        #include <map>
        #include <unordered_set>
        #include <unordered_map>
        #include <queue>
        #include <ctime>
        #include <cassert>
        #include <complex>
        #include <string>
        #include <cstring>
        #include <chrono>
        #include <random>
        #include <bitset>
        #include <array>
        #include <iomanip>
        using namespace std;
         
        //#pragma GCC optimize("O3,unroll-loops")
        //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
         
        /*
        #include <ext/pb_ds/assoc_container.hpp>
        using namespace __gnu_pbds;
        template <class T>
        using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        */
         
         
        #define rep(i, n) for (int i = 0; i < (n); ++i)
        #define rep1(i, n) for (int i = 1; i < (n); ++i)
        #define rep1n(i, n) for (int i = 1; i <= (n); ++i)
        #define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
         
         
        #define fr first
        #define sc second
        #define pb push_back
        #define mp make_pair
        #define all(x) (x).begin(), (x).end()
        #define rall(x) (x).rbegin(), (x).rend()
        #define endl '\n'
         
         
        using lint = long long;
        using ulint = unsigned long long;
        using ld = long double;
        using str = string;
        using pi = pair<int, int>;
         
         
        using vi = vector<int>;
        using vl = vector<lint>;
        using vpi = vector<pair<int, int>>;
        using vvi = vector<vi>;
         
        const int mod = (int)1e9 + 7;
         
        vector<pair<lint,lint>> unq;
        vl W(200000);
         
        struct CHT{
            struct Line{
                lint m,y;
                Line(lint a, lint b): m(a), y(b){}
         
                lint eval(lint x){
                    return x * m + y;
                }
         
                lint intercept(Line& b){
                    //m2x + c2 = m1x + c1
                    //x * (m2 - m1) = c1 - c2
                    //x = (c1 - c2) / (m2 - m1)
                    return (y - b.y + (b.m - m - 1)) / (b.m - m);
                }
            };
            deque<pair<Line,pair<lint,lint>>>dq;
         
            void insert(lint m, lint y, int c){
                Line New_Line(m,y);
                while(dq.size() > 1){
                    if (dq[dq.size() - 2].fr.intercept(New_Line) <= dq.back().sc.fr){
                        dq.pop_back();
                    }else{
                        break;
                    }
                }
         
                if (dq.empty()){
                    dq.push_back({New_Line, {-(lint)1e14,c}});
                }else{
                    dq.push_back({New_Line, {New_Line.intercept(dq.back().fr),c}});
                }
            }
         
            pair<lint,lint>query(lint x){
                while(dq.size() > 1 && dq[1].sc.fr <= x)dq.pop_front();
                return {dq[0].fr.eval(x), dq[0].sc.sc + 0};
            }
        };
         
        pair<lint,lint> Lagrangian_Relaxation(lint lambda, lint k){
                    CHT vals;
                    vector<long long> dp(unq.size()+1);
                    vector<int> cnt(unq.size()+1);
                    for(int i = 1;i<=unq.size();i++){
                        long long val = dp[i-1] + unq[i-1].second * unq[i-1].second - 2*unq[i-1].second;
                        if(i > 1)
                            val -= max(0ll,unq[i-2].first - unq[i-1].second + 1) *  max(0ll,unq[i-2].first - unq[i-1].second + 1);
                        
                        vals.insert(-2*unq[i-1].second,val,cnt[i-1]);
                        auto x = vals.query(unq[i-1].first);
                        dp[i] = x.first + unq[i-1].first * unq[i-1].first + 2 * unq[i-1].first + 1 + lambda;
                        cnt[i] = x.second + 1;
                    } 
                    return make_pair(cnt[unq.size()],dp[unq.size()] - k * lambda);
                
            \
        }
         
        long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
            
            vector<pair<lint,lint>> Segments;
            rep(i,n){
                Segments.push_back(mp(min(r[i], c[i]), max(r[i], c[i])));
            }
            sort(all(Segments), [&](auto x, auto y){
                if (x.fr < y.fr)return true;
                else if (x.fr == y.fr)return x.sc > y.sc;
                else return false;
            });
         
            int most_right = -1;
            vi marked(n,0);
            rep(i,n){
                if (most_right >= Segments[i].sc){
                    marked[i] = 1;
                }
                most_right = max((lint)most_right, Segments[i].second);
            }
            rep(i,n){
                if (!marked[i]){
                    unq.pb(Segments[i]);
                }
            }
            for (auto& i : unq){
                swap(i.fr,i.sc);
            }
            lint L = 0, R = m * m;
            while(L <= R){
                lint mid = (L+R) / 2;
                if (Lagrangian_Relaxation(mid,k).fr <= k){
                    R = mid - 1;
                }else{
                    L = mid + 1;
                }
            }
            return Lagrangian_Relaxation(R + 1,k).sc;
        }

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

aliens.cpp: In function 'std::pair<long long int, long long int> Lagrangian_Relaxation(lint, lint)':
aliens.cpp:112:36: 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 = 1;i<=unq.size();i++){
      |                                   ~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40