Submission #935178

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
935178	2024-02-28 18:55:21	kim	Chorus (JOI23_chorus)	C++17	100 / 100	1444 ms	55672 KiB

chorus

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;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
const ll inf=1e18;
int a[1000005],b[1000005],pos[1000005],pos2[1000005];
ll qs[1000005];
pair<ll,int> dp2[1000005];
struct line{
    ll m,c;
    int cnt;
    line(ll m,ll c,int cnt):m(m),c(c),cnt(cnt){}
    ll operator()(const ll x)const{return m*x+c;}
};
struct cht{
    deque<line> dq;
    bool check(line a,line b,line c){
        return (a.c-b.c)*(c.m-a.m)>=(a.c-c.c)*(b.m-a.m);
    }
    void insert(ll m,ll c,int cnt){
        line f(m,c,cnt);
        while(dq.size()>1&&check(dq.end()[-2],dq.back(),f)) dq.pop_back();
        dq.eb(f);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0,ia=0,ib=0;i<s.length();++i){
      |                           ~^~~~~~~~~~~
chorus.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         ll mid=l+r>>1;
      |                ~^~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 26 / 26
• Subtask 5: 13 / 13