Submission #584999

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
584999	2022-06-28 08:23:06	mosiashvililuka	Discharging (NOI20_discharging)	C++14	100 / 100	288 ms	107092 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;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],dp[1000009],K,B,X,z;
deque <pair <long long, long long > > de;
pair <long long, long long> seg[4000009];
deque <pair <long long, pair <long long, long long> > > SEG;
void upd(long long q, long long w, long long rr){
    if(q>w) return;
    if(seg[rr]==make_pair(-1LL,-1LL)){
        SEG.push_back({rr,{seg[rr].first,seg[rr].second}});
        seg[rr]={K,B};
        return;
    }
    long long mid=(q+w)/2;
    if(seg[rr].first*mid+seg[rr].second>K*mid+B){
        SEG.push_back({rr,{seg[rr].first,seg[rr].second}});
        swap(seg[rr].first,K);swap(seg[rr].second,B);
    }
    if(seg[rr].first*q+seg[rr].second>K*q+B){
        upd(q,mid-1,rr*2);
    }else{
        if(seg[rr].first*w+seg[rr].second>K*w+B){
            upd(mid+1,w,rr*2+1);
        }
    }
}
void read(long long q, long long w, long long rr){
    if(q>w) return;
    if(q==w){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

Discharging.cpp: In function 'void rollback(long long int)':
Discharging.cpp:44:21: warning: comparison of integer expressions of different signedness: 'std::deque<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |     while(SEG.size()>q){
      |           ~~~~~~~~~~^~

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