oj.uz

Submission #1094020

# Submission time Handle Problem Language Result Execution time Memory
1094020 2024-09-28T10:14:38 Z 8pete8 Two Dishes (JOI19_dishes) C++17
10 / 100
 10000 ms 42036 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
const int mod=998244353,mxn=1e6+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m,q;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
pair<int,pii> v1[mxn+10],v2[mxn+10];
//time,before,point
int gap[mxn+10],dp[mxn+10],suf[mxn+10];
struct seg{
    int v[4*mxn+10],lazy1[4*mxn+10],lazy2[4*mxn+10];
    void init(){for(int i=0;i<=4*(n+1);i++)lazy2[i]=inf;}
    void push(int l,int r,int pos){
        if(lazy2[pos]!=inf)v[pos]=lazy2[pos];
        v[pos]+=lazy1[pos];
        if(l!=r){
            if(lazy2[pos]!=inf)lazy1[pos*2+1]=0,lazy1[pos*2]=0;
            lazy1[pos*2+1]+=lazy1[pos];
            lazy1[pos*2]+=lazy1[pos];
            if(lazy2[pos]!=inf){
                lazy2[pos*2+1]=lazy2[pos];
                lazy2[pos*2]=lazy2[pos];
            }
        }
        lazy2[pos]=inf;
        lazy1[pos]=0;
    }
    void updateadd(int l,int r,int ql,int qr,int val,int pos){
        push(l,r,pos);
        if(l>qr||r<ql)return;
        if(l>=ql&&r<=qr){
            lazy1[pos]+=val;
            push(l,r,pos);
            return;
        }
        int mid=l+(r-l)/2;
        updateadd(l,mid,ql,qr,val,pos*2);
        updateadd(mid+1,r,ql,qr,val,pos*2+1);
        v[pos]=max(v[pos*2],v[pos*2+1]);
    }
    void updateset(int l,int r,int ql,int qr,int val,int pos){
        push(l,r,pos);
        if(l>qr||r<ql)return;
        if(l>=ql&&r<=qr){
            lazy2[pos]=val;
            push(l,r,pos);
            return;
        }
        int mid=l+(r-l)/2;
        updateset(l,mid,ql,qr,val,pos*2);
        updateset(mid+1,r,ql,qr,val,pos*2+1);
        v[pos]=max(v[pos*2],v[pos*2+1]);
    }
    int qry(int l,int r,int qpos,int pos){
        push(l,r,pos);
        if(l==r)return v[pos];
        int mid=l+(r-l)/2;
        if(qpos<=mid)return qry(l,mid,qpos,pos*2);
        return qry(mid+1,r,qpos,pos*2+1);
    }
}t;
int getbound(int x,int add){
	int l=0,r=n,pos=-1;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(v1[mid].f+add<=x)l=mid+1,pos=max(pos,mid);
		else r=mid-1;
	}
	return pos;
}
int getpos(int x,int st){
    int l=st,r=n,pos=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(t.qry(0,n,mid,1)<x)l=mid+1,pos=max(pos,mid);
        else r=mid-1;
    }
    return pos;
}
int32_t main(){
    fastio
    //n^2 can use lazy seg to op
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v1[i].f>>v1[i].s.f>>v1[i].s.s;
		v1[i].f+=v1[i-1].f;
	}
	for(int i=1;i<=m;i++){
		cin>>v2[i].f>>v2[i].s.f>>v2[i].s.s;
		v2[i].f+=v2[i-1].f;
	}
	int ans1=0,ans2=0;
	vector<pii>gap;
	for(int i=1;i<=n;i++){
		if(v1[i].f<=v1[i].s.f){
			gap.pb({v1[i].s.f-v1[i].f,i});
			ans1+=v1[i].s.s;
		}
	}
    t.init();
	sort(all(gap));
	int cur=0;
	for(int j=1;j<=m;j++){
		int x=getbound(v2[j].s.f,v2[j].f);
        if(x!=-1)t.updateadd(0,n,0,x,v2[j].s.s,1);
		for(int i=0;i<=x;i++)dp[i]+=v2[j].s.s;
		while(cur<gap.size()&&gap[cur].f<v2[j].f){
            t.updateadd(0,n,0,gap[cur].s-1,-v1[gap[cur].s].s.s,1);
			cur++;
		}
        t.push(0,n,1);
        ans2=max(ans2,t.v[1]);
        int bruh=t.qry(0,n,x,1);
        int where=getpos(bruh,x+1);
        if(where!=-1)t.updateset(0,n,x+1,where,bruh,1);
	}
    cout<<ans1+ans2<<'\n';
}
/*

*/

Compilation message

dishes.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
dishes.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void setIO(string name){
      |                       ^
dishes.cpp:49:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 |     void init(){for(int i=0;i<=4*(n+1);i++)lazy2[i]=inf;}
      |               ^
dishes.cpp:50:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 |     void push(int l,int r,int pos){
      |                                  ^
dishes.cpp:65:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 |     void updateadd(int l,int r,int ql,int qr,int val,int pos){
      |                                                             ^
dishes.cpp:78:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 |     void updateset(int l,int r,int ql,int qr,int val,int pos){
      |                                                             ^
dishes.cpp:91:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   91 |     int qry(int l,int r,int qpos,int pos){
      |                                         ^
dishes.cpp:99:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   99 | int getbound(int x,int add){
      |                           ^
dishes.cpp:108:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  108 | int getpos(int x,int st){
      |                        ^
dishes.cpp:117:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  117 | int32_t main(){
      |              ^
dishes.cpp: In function 'int32_t main()':
dishes.cpp:144:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |   while(cur<gap.size()&&gap[cur].f<v2[j].f){
      |         ~~~^~~~~~~~~~~
dishes.cpp: In function 'void setIO(std::string)':
dishes.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6053 ms 42036 KB Output is correct
2 Correct 8926 ms 41452 KB Output is correct
3 Execution timed out 10026 ms 34244 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 5 ms 860 KB Output is correct
20 Correct 3 ms 788 KB Output is correct
21 Correct 4 ms 812 KB Output is correct
22 Correct 4 ms 848 KB Output is correct
23 Correct 4 ms 600 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 5 ms 860 KB Output is correct
20 Correct 3 ms 788 KB Output is correct
21 Correct 4 ms 812 KB Output is correct
22 Correct 4 ms 848 KB Output is correct
23 Correct 4 ms 600 KB Output is correct
24 Correct 7477 ms 39528 KB Output is correct
25 Correct 461 ms 28620 KB Output is correct
26 Correct 7381 ms 39796 KB Output is correct
27 Correct 7475 ms 38252 KB Output is correct
28 Execution timed out 10095 ms 39356 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 5 ms 860 KB Output is correct
20 Correct 3 ms 788 KB Output is correct
21 Correct 4 ms 812 KB Output is correct
22 Correct 4 ms 848 KB Output is correct
23 Correct 4 ms 600 KB Output is correct
24 Correct 7477 ms 39528 KB Output is correct
25 Correct 461 ms 28620 KB Output is correct
26 Correct 7381 ms 39796 KB Output is correct
27 Correct 7475 ms 38252 KB Output is correct
28 Execution timed out 10095 ms 39356 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 5 ms 860 KB Output is correct
20 Correct 3 ms 788 KB Output is correct
21 Correct 4 ms 812 KB Output is correct
22 Correct 4 ms 848 KB Output is correct
23 Correct 4 ms 600 KB Output is correct
24 Correct 7477 ms 39528 KB Output is correct
25 Correct 461 ms 28620 KB Output is correct
26 Correct 7381 ms 39796 KB Output is correct
27 Correct 7475 ms 38252 KB Output is correct
28 Execution timed out 10095 ms 39356 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6053 ms 42036 KB Output is correct
2 Correct 8926 ms 41452 KB Output is correct
3 Execution timed out 10026 ms 34244 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6053 ms 42036 KB Output is correct
2 Correct 8926 ms 41452 KB Output is correct
3 Execution timed out 10026 ms 34244 KB Time limit exceeded
4 Halted 0 ms 0 KB -