Submission #837053

#	Time	Username	Problem	Language	Result	Execution time	Memory
837053		Ellinor	Aliens (IOI16_aliens)	C++14	0 / 100	2050 ms	340 KiB

aliens

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <cstdlib>
#include <set>
#include <iomanip>
#include <limits>
#include <map>
#include <assert.h>
#include <algorithm>
#include <list>
#include <iterator>
#include <fstream>
#include <random>
#include <unordered_map>
#include <array>
//#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for (int i = (a); i < b; i++)
#define rrep(i,a) for (int i = (a) - 1; i >= 0; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<bool, bool> pbb;

// fast

#include "aliens.h" // !!!

//

int N, M;
vector<int> diagonal;

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) 
{
    N = n;
    M = m;
    diagonal.assign(M, 0); // -1 ?

    rep(i,0,N)
    {
        int d = min(r[i], c[i]);
        int da = max(r[i], c[i]) - min(r[i], c[i]) + 1; // +1 // 0-ind
        diagonal[d] = max(diagonal[d], da);
    }

    int d = 0;
    rep(i,0,M)
    {
        d--;
        // d = max(d, 0);
        d = max(d, diagonal[i]);
        diagonal[i] = d;
    }

    set<pii> square_start_inds;

    int last = 0;
    rep(i,0,M)
    {
        if (diagonal[i] > last)
        {
            // start of square
            square_start_inds.insert({i, diagonal[i]});

            last = diagonal[i];
        }
        last--;
    }

    // squares > 0

    assert(k==n);
    
    if (square_start_inds.size() > k)
    {
        // diff // diff, start_ind_1, start_ind_2
        set<array<ll, 3>> diff_set;
        map<pii, ll> diff_map; // ??

        auto it = square_start_inds.begin();
        pii x = *it;

        int last_ind = x.first;
        int last_len = x.second;

        int now_ind, now_len;

        for (auto it = square_start_inds.begin(); it != square_start_inds.end(); it++)
        {
            it++;

            x = *it;
            now_ind = x.first;
            now_len = x.second;

            ll diff = 0;
            ll side = now_ind + now_len - last_ind; // 1 1
            ll add = side * side;
            diff += add;

            ll rem = last_len * last_len;
            diff -= rem;

            rem = now_len * now_len;
            diff -= rem;

            //

            diff_set.insert({diff, last_ind, now_ind});
            diff_map[{last_ind, now_ind}] = diff;

            //

            last_ind = x.first;
            last_len = x.second;
        }

        while (square_start_inds.size() > k)
        {
            auto it = diff_set.begin();
            array<ll, 3> arr = *it;
            ll diff = arr[0];
            ll ind_1 = arr[1];
            ll ind_2 = arr[2];
            diff_set.erase(it); // !

            ll ind_2_len;

            ll ind_before, len_before;
            auto itt = square_start_inds.lower_bound({ind_1, 0});
            if (itt != square_start_inds.begin())
            {
                itt--;
                pii x = *itt;
                ind_before = x.first;
                len_before = x.second;

                ll diff1 = diff_map[{ind_before, ind_1}];
                auto it1 = diff_set.lower_bound({diff1, ind_before, ind_1});
                // assert !
                diff_set.erase(it1);

                // square_start_inds.erase(itt); // bort nej

                // ta bort diff
            }
            // else ?

            ll ind_after, len_after;
            // ta bort diff
            // ???
            itt = square_start_inds.lower_bound({ind_2, 0});
            // !
            pii xx = *itt;
            ind_2_len = xx.second;

            if (itt != square_start_inds.end())
            {
                itt++;
                if (itt != square_start_inds.end())
                {
                    pii x = *itt;
                    ind_after = x.first;
                    len_after = x.second;

                    ll diff2 = diff_map[{ind_2, ind_after}];
                    auto it2 = diff_set.lower_bound({diff2, ind_2, ind_after});
                    // assert !
                    diff_set.erase(it2);

                    // square_start_inds.erase(itt); // bort nej

                    // ta bort diff
                }
            }

            ll my_len = ind_2 + ind_2_len - ind_1;

            // add new diff 1
            last_ind = ind_before;
            last_len = len_before;

            now_ind = ind_1;
            now_len = my_len;

            ll diff_ = 0;
            ll side = now_ind + now_len - last_ind; // 1 1
            ll add = side * side;
            diff_ += add;

            ll rem = last_len * last_len;
            diff_ -= rem;

            rem = now_len * now_len;
            diff_ -= rem;

            diff_set.insert({diff_, last_ind, now_ind});
            diff_map[{last_ind, now_ind}] = diff_;

            // add new diff 2

            last_ind = ind_1;
            last_len = my_len;

            now_ind = ind_after;
            now_len = len_after;

            diff_ = 0;
            side = now_ind + now_len - last_ind; // 1 1
            add = side * side;
            diff_ += add;

            rem = last_len * last_len;
            diff_ -= rem;

            rem = now_len * now_len;
            diff_ -= rem;

            diff_set.insert({diff_, last_ind, now_ind});
            diff_map[{last_ind, now_ind}] = diff_;

            // ta bort square_inds * 2, add * 1

            // ta bort 1
            auto it3 = square_start_inds.lower_bound({ind_1, 0});
            // ?
            square_start_inds.erase(it3);

            // ta bort 2
            // ???
            it3 = square_start_inds.lower_bound({ind_2, 0});
            // ?
            square_start_inds.erase(it3);

            // add 1
            square_start_inds.insert({ind_1, my_len});
        }
    }

    ll ans = 0;
    ll last_reach = -1;
    for (auto it = square_start_inds.begin(); it != square_start_inds.end(); it++)
    {
        pii x = *it;

        ll add = x.second * x.second;
        ans += add;

        if (last_reach >= x.first)
        {
            int overlap = last_reach - x.first + 1;

            ll rem = overlap * overlap;
            ans -= rem;
        }

        last_reach = x.first + x.second - 1;
    }

    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:81:34: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     if (square_start_inds.size() > k)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
aliens.cpp:125:41: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |         while (square_start_inds.size() > k)
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
aliens.cpp:129:16: warning: unused variable 'diff' [-Wunused-variable]
  129 |             ll diff = arr[0];
      |                ^~~~
aliens.cpp:187:22: warning: 'ind_before' may be used uninitialized in this function [-Wmaybe-uninitialized]
  187 |             last_ind = ind_before;
      |             ~~~~~~~~~^~~~~~~~~~~~
aliens.cpp:212:21: warning: 'ind_after' may be used uninitialized in this function [-Wmaybe-uninitialized]
  212 |             now_ind = ind_after;
      |             ~~~~~~~~^~~~~~~~~~~
aliens.cpp:213:21: warning: 'len_after' may be used uninitialized in this function [-Wmaybe-uninitialized]
  213 |             now_len = len_after;
      |             ~~~~~~~~^~~~~~~~~~~
aliens.cpp:188:22: warning: 'len_before' may be used uninitialized in this function [-Wmaybe-uninitialized]
  188 |             last_len = len_before;
      |             ~~~~~~~~~^~~~~~~~~~~~

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