Submission #712889

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
712889	2023-03-20 10:23:25	minhnhatnoe	Aliens (IOI16_aliens)	C++14	100 / 100	1116 ms	11364 KiB

aliens

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sq(ll a) {return a * a;}
struct lichao_tree{
    struct node{
        pair<ll, ll> line;
        int cnt = 0;
        int l = -1, r = -1;
        node(ll a, ll b, int cnt): line(a, b), cnt(cnt) {}
        ll eval(ll x){
            return line.first * x + line.second;
        }
    };
    int L, R;
    lichao_tree(int lrange, int rrange): L(lrange), R(rrange) {}
    vector<node> g;
    void insert(ll a, ll b, int cnt){
        if (g.size() == 0){
            g.emplace_back(a, b, cnt);
            return;
        }
        int tidx = 0;
        int tl = L, tr = R;
        node tmp(a, b, cnt);
        while (true){
            int tm = (tl + tr)>>1;
            bool left = g[tidx].eval(tl) > tmp.eval(tl);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, int> alien_solve(const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:80:20: 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]
   80 |     for (int i=0; i<p.size(); i++){
      |                   ~^~~~~~~~~

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