Submission #321055

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
321055	2020-11-10 19:14:40	saarang123	Discharging (NOI20_discharging)	C++14	100 / 100	149 ms	17508 KiB

Discharging

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 <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e15;
const int N = 1502;
struct CHT {
    struct Line {
        int slope, c; //slope, yIntercept
        Line(int slope, int c) : slope(slope), c(c) {}
        int val(int xCoordinate) { return slope * xCoordinate + c; }  //y coordinate
        int intersect(Line other) {  //ceiling of x coordinate of intersection
            return (other.c - c + slope - other.slope - 1) / (slope - other.slope);
        }
    };
    //Similar to monotonic queue
    deque<pair<Line, int>> dq;   //used to maintain the CHT
    void add(int slope, int yIntersect) { //add new line
        Line newLine(slope, yIntersect);
        while(dq.size() > 1 && dq.back().second >= dq.back().first.intersect(newLine)) // <= if max is optimal
            dq.pop_back();  //pop redundant(not optimal) lines
        if(dq.empty())
            dq.push_back(make_pair(newLine, 0)); //set 0 to -inf if -ve
        else
            dq.push_back(make_pair(newLine, dq.back().first.intersect(newLine)));
    }
    int qry(int xCoordinate) { //only if queries are monotonic - O(1) on average
        while(dq.size() > 1) {
            if(dq[1].second <= xCoordinate) dq.pop_front(); //finding optimal range for xCoord
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28