Submission #968875

#	Time	Username	Problem	Language	Result	Execution time	Memory
968875		modwwe	Cake 3 (JOI19_cake3)	C++17	100 / 100	2620 ms	30240 KiB

cake3

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void ngha();
const int mod2 = 1e9 + 7;
const int  mod1 = 998244353;
struct ib
{
    int a;
    int b;
};
struct icd
{
    int a, b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
int n, m, s1, s2, s4, s3, sf, k, r, mid, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, l;
int  i, s10, s12;
int el = 29;
main()
{
//#ifndef ONLINE_JUDGE
    //   fin(task),fou(task);
//#endif
    NHP
//modwwe
    //  cin>>res;
    ngha(), down
    checktime
}
bool cmp(ib a, ib b)
{
    return a.b < b.b;
}
vector<int> v;
ic t[800001];
ib t2[800001];
ib a[2000001];
void build(int node, int l, int r)
{
    t[node].c = n + 1;
    if(l == r)
        return;
    int mid = l + r >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
}
void upd(int node, int l, int r, int l1, int r1, int x)
{
    if(l > r1 || r < l1)
        return;
    if(l >= l1 && r <= r1)
    {
        t[node].b += x;
        t[node].a = t[node].b * v[l-1];
        if(t[node].b == 0)
            t[node].c = n + 1;
        else
            t[node].c = l;
        return;
    }
    int mid = l + r >> 1;
    upd(node << 1, l, mid, l1, r1, x);
    upd(node << 1 | 1, mid + 1, r, l1, r1, x);
    t[node].c = min(t[node << 1].c, t[node << 1 | 1].c);
    t[node].b = t[node << 1].b + t[node << 1 | 1].b;
    t[node].a = t[node << 1].a + t[node << 1 | 1].a;
}
void upd2(int node, int l, int r, int l1, int r1, int x)
{
    if(l > r1 || r < l1)
        return;
    if(l >= l1 && r <= r1)
    {
        t2[node].b += x;
        if(t2[node].b != 0)
            t2[node].a = l;
        else
            t2[node].a = 0;
        return;
    }
    int mid = l + r >> 1;
    upd2(node << 1, l, mid, l1, r1, x);
    upd2(node << 1 | 1, mid + 1, r, l1, r1, x) ;
    t2[node].a = max(t2[node << 1].a, t2[node << 1 | 1].a);
}
void del(int f)
{
    if(t[1].c <= f)
    {
        upd(1, 1, n, f, f, -1);
        if(t2[1].a > 0)
        {
            upd(1, 1, n, t2[1].a, t2[1].a, 1);
            upd2(1, 1, n, t2[1].a, t2[1].a, -1);
        }
    }
    else
    {
        upd2(1, 1, n, f, f, -1);
    }
}
/// a be nhat
void ff(int f)
{
    if(t[1].b < m){
        upd(1, 1, n, f, f, 1);
    return;}
    else if(t[1].c < f)
    {int sss=t[1].c;
        upd(1, 1, n, f, f, 1);
        upd2(1, 1, n, sss, sss, 1);
        upd(1, 1, n, sss, sss, -1);
    return;
    }
    else
    {
        upd2(1, 1, n, f, f, 1);
    return;
    }
}
void up(int x, int y)
{
      while(l > x)
    {
        l--;
        ff(a[l].a);
    }

    while(r < y)
    {
        r++;
        ff(a[r].a);
    }

    while(r > y)
    {
        del(a[r].a);
        r--;
    }
 while(l < x)
    {
        del(a[l].a);
        l++;
    }

}
void calc(int x, int y, int l2, int r2)
{
    if(x > y)
        return;
    int mid = x + y >> 1;
    int ssf = -1e18, cc = 0;
    for(int i = max(mid + m - 1, l2); i <= r2; i++)
    {
        up(mid, i);
        if(t[1].a - a[i].b * 2 + a[mid].b * 2 > ssf)
            ssf = t[1].a - a[i].b * 2 + a[mid].b * 2,
            cc = i;
    }
   /// cout<<x<<" "<<y<<" "<<ssf<<" "<<t[1].b<<" "<<l<<" "<<r,down
    s4 = max(s4, ssf);
    calc(mid + 1, y, cc, r2);
    calc(x, mid - 1, l2, cc);
}
void ngha()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i].a >> a[i].b, v.pb(a[i].a);
    sort(a + 1, a + 1 + n, cmp);
    sort(v.begin(), v.end()) ;
    for(i = 1; i <= n; i++)
        a[i].a = lower_bound(v.begin(), v.end(), a[i].a) - v.begin() + 1;
  build(1,1,n);
    l = 1;
    r = 0;
    s4 = -1e18;
    calc(1, n - m + 1, m, n);
    cout << s4;
}

Compilation message (stderr)

cake3.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
cake3.cpp: In function 'void build(long long int, long long int, long long int)':
cake3.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = l + r >> 1;
      |               ~~^~~
cake3.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |     int mid = l + r >> 1;
      |               ~~^~~
cake3.cpp: In function 'void upd2(long long int, long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:107:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |     int mid = l + r >> 1;
      |               ~~^~~
cake3.cpp: In function 'void calc(long long int, long long int, long long int, long long int)':
cake3.cpp:177:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  177 |     int mid = x + y >> 1;
      |               ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76