oj.uz

답안 #372492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372492 2021-02-28T12:30:40 Z denkendoemeer 모임들 (IOI18_meetings) C++14
100 / 100
 3329 ms 324516 KB 
#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct lc
{
	int a,l,r;
	ll b,lazy;
	lc():a(0),l(0),r(0),b(0x3fffffffffffffffLL),lazy(0){}
};
pair<int,int>aint[1<<21];
lc lt[1<<21],rt[1<<21];
vector<long long>ans;
vector<tuple<int,int,int>>q[750001];
pair<int,int> calc(int st,int dr)
{
	pair<int,int>rez(-1,-1);
	for(st+=1<<20,dr+=1<<20;st<=dr;st>>=1,dr>>=1){
		if (st&1)
            rez=max(rez,aint[st++]);
		if (~dr&1)
            rez=max(rez,aint[dr--]);
	}
	return rez;
}
void push(lc *aint,int nod,int st,int dr)
{
	if (aint[nod].lazy){
		aint[nod].b+=aint[nod].lazy;
		if (st<dr){
			aint[2*nod].lazy+=aint[nod].lazy;
			aint[2*nod+1].lazy+=aint[nod].lazy;
		}
		aint[nod].lazy=0;
	}
}
int semn(ll x)
{
    if (x<0)
        return -1;
    return x>0;
}
void addlin(lc *aint,int l,int r,int a,long long b,int nod=1,int st=0,int dr=(1<<20)-1)
{
	int mij=(st+dr)/2;
	push(aint,nod,st,dr);
	if (r<l || r<st || dr<l)
        return;
	if (l<=st && dr<=r){
		ll st2=1LL*a*st+b,mij2=1LL*a*mij+b,dr2=1LL*a*dr+b,st3=1LL*aint[nod].a*st+aint[nod].b,mij3=1LL*aint[nod].a*mij+aint[nod].b,dr3=1LL*aint[nod].a*dr+aint[nod].b;
		if (mij2<mij3){
			swap(aint[nod].a,a);
            swap(aint[nod].b,b);
			swap(st3,st2);
			swap(mij3,mij2);
			swap(dr3,dr2);
		}
		if (st3<=st2 && dr3<=dr2)
            return;
		if (semn(st2-st3)*semn(mij2-mij3)<0 || mij2==mij3 && st2<st3)
            addlin(aint,l,r,a,b,2*nod,st,mij);
		else
            addlin(aint,l,r,a,b,2*nod+1,mij+1,dr);
		return;
	}
	addlin(aint,l,r,a,b,2*nod,st,mij);
	addlin(aint,l,r,a,b,2*nod+1,mij+1,dr);
}
void add(lc *aint,int l,int r,ll val,int nod=1,int st=0,int dr=(1<<20)-1)
{
	int mij=(st+dr)/2;
	push(aint,nod,st,dr);
	if (r<l || r<st || dr<l)
        return;
	if (l<=st && dr<=r){
		aint[nod].lazy=val;
		push(aint,nod,st,dr);
		return;
	}
	add(aint,l,r,val,2*nod,st,mij);
	add(aint,l,r,val,2*nod+1,mij+1,dr);
}
long long calcy(lc *aint,int poz,int nod=1,int st=0,int dr=(1<<20)-1)
{
	int mij=(st+dr)/2;
	push(aint,nod,st,dr);
	if (st==dr)
        return 1LL*aint[nod].a*poz+aint[nod].b;
	return min(poz<=mij?calcy(aint,poz,2*nod,st,mij):calcy(aint,poz,2*nod+1,mij+1,dr),1LL*aint[nod].a*poz+aint[nod].b);
}
void solve(int st,int dr)
{
	if (st>dr)
        return;
	auto [a,b]=calc(st,dr);
	solve(st,b-1);
	solve(b+1,dr);
	for(auto [l,r,i]:q[b])
        ans[i]=min(calcy(lt,l)+(r-b+1LL)*a,calcy(rt,r)+(b-l+1LL)*a);
	add(lt,st,b-1,(dr-b+1LL)*a);
	if (b<dr)
        addlin(lt,st,b,-a,calcy(lt,b+1)+a*(b+1LL));
    else
        addlin(lt,st,b,-a,a*(b+1LL));
	add(rt,b+1,dr,(b-st+1LL)*a);
	if (st<b)
        addlin(rt,b,dr,a,calcy(rt,b-1)+a*(1LL-b));
    else
        addlin(rt,b,dr,a,a*(1LL-b));
}
vector<long long> minimum_costs(vector<int>H,vector<int>L,vector<int>R)
{
	int n=H.size(),m=L.size();
	ans.resize(m);
	int i;
	for(i=0;i<n;i++)
        aint[(1<<20)+i+1]={H[i],i+1};
	for(i=(1<<20);--i;)
        aint[i]=max(aint[2*i],aint[2*i+1]);
	for(i=0;i<m;i++){
		if (++L[i]<++R[i])
            q[calc(L[i],R[i]).second].emplace_back(L[i],R[i],i);
		else
            ans[i]=H[L[i]-1];
	}
	solve(1,n);
	return ans;
}

Compilation message

meetings.cpp: In function 'void addlin(lc*, int, int, int, long long int, int, int, int)':
meetings.cpp:60:53: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |   if (semn(st2-st3)*semn(mij2-mij3)<0 || mij2==mij3 && st2<st3)
      |                                          ~~~~~~~~~~~^~~~~~~~~~
meetings.cpp: In function 'void solve(int, int)':
meetings.cpp:95:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |  auto [a,b]=calc(st,dr);
      |       ^
meetings.cpp:98:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for(auto [l,r,i]:q[b])
      |           ^
meetings.cpp:103:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  103 |     else
      |     ^~~~
meetings.cpp:105:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  105 |  add(rt,b+1,dr,(b-st+1LL)*a);
      |  ^~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 157548 KB Output is correct
2 Correct 98 ms 157548 KB Output is correct
3 Correct 108 ms 157676 KB Output is correct
4 Correct 103 ms 157548 KB Output is correct
5 Correct 98 ms 157504 KB Output is correct
6 Correct 99 ms 157932 KB Output is correct
7 Correct 101 ms 157676 KB Output is correct
8 Correct 99 ms 157804 KB Output is correct
9 Correct 100 ms 157676 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 157548 KB Output is correct
2 Correct 98 ms 157548 KB Output is correct
3 Correct 108 ms 157676 KB Output is correct
4 Correct 103 ms 157548 KB Output is correct
5 Correct 98 ms 157504 KB Output is correct
6 Correct 99 ms 157932 KB Output is correct
7 Correct 101 ms 157676 KB Output is correct
8 Correct 99 ms 157804 KB Output is correct
9 Correct 100 ms 157676 KB Output is correct
10 Correct 122 ms 158060 KB Output is correct
11 Correct 107 ms 158060 KB Output is correct
12 Correct 107 ms 158060 KB Output is correct
13 Correct 105 ms 158060 KB Output is correct
14 Correct 108 ms 158316 KB Output is correct
15 Correct 105 ms 158060 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 157696 KB Output is correct
2 Correct 187 ms 161336 KB Output is correct
3 Correct 424 ms 172396 KB Output is correct
4 Correct 404 ms 166156 KB Output is correct
5 Correct 303 ms 170476 KB Output is correct
6 Correct 394 ms 174188 KB Output is correct
7 Correct 447 ms 175784 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 157696 KB Output is correct
2 Correct 187 ms 161336 KB Output is correct
3 Correct 424 ms 172396 KB Output is correct
4 Correct 404 ms 166156 KB Output is correct
5 Correct 303 ms 170476 KB Output is correct
6 Correct 394 ms 174188 KB Output is correct
7 Correct 447 ms 175784 KB Output is correct
8 Correct 389 ms 166656 KB Output is correct
9 Correct 331 ms 166404 KB Output is correct
10 Correct 350 ms 166636 KB Output is correct
11 Correct 384 ms 165996 KB Output is correct
12 Correct 339 ms 165860 KB Output is correct
13 Correct 356 ms 166380 KB Output is correct
14 Correct 405 ms 172780 KB Output is correct
15 Correct 363 ms 165796 KB Output is correct
16 Correct 419 ms 172780 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 157548 KB Output is correct
2 Correct 98 ms 157548 KB Output is correct
3 Correct 108 ms 157676 KB Output is correct
4 Correct 103 ms 157548 KB Output is correct
5 Correct 98 ms 157504 KB Output is correct
6 Correct 99 ms 157932 KB Output is correct
7 Correct 101 ms 157676 KB Output is correct
8 Correct 99 ms 157804 KB Output is correct
9 Correct 100 ms 157676 KB Output is correct
10 Correct 122 ms 158060 KB Output is correct
11 Correct 107 ms 158060 KB Output is correct
12 Correct 107 ms 158060 KB Output is correct
13 Correct 105 ms 158060 KB Output is correct
14 Correct 108 ms 158316 KB Output is correct
15 Correct 105 ms 158060 KB Output is correct
16 Correct 94 ms 157696 KB Output is correct
17 Correct 187 ms 161336 KB Output is correct
18 Correct 424 ms 172396 KB Output is correct
19 Correct 404 ms 166156 KB Output is correct
20 Correct 303 ms 170476 KB Output is correct
21 Correct 394 ms 174188 KB Output is correct
22 Correct 447 ms 175784 KB Output is correct
23 Correct 389 ms 166656 KB Output is correct
24 Correct 331 ms 166404 KB Output is correct
25 Correct 350 ms 166636 KB Output is correct
26 Correct 384 ms 165996 KB Output is correct
27 Correct 339 ms 165860 KB Output is correct
28 Correct 356 ms 166380 KB Output is correct
29 Correct 405 ms 172780 KB Output is correct
30 Correct 363 ms 165796 KB Output is correct
31 Correct 419 ms 172780 KB Output is correct
32 Correct 2566 ms 224744 KB Output is correct
33 Correct 1953 ms 223684 KB Output is correct
34 Correct 2161 ms 227760 KB Output is correct
35 Correct 2580 ms 227380 KB Output is correct
36 Correct 1958 ms 225460 KB Output is correct
37 Correct 2161 ms 228128 KB Output is correct
38 Correct 2954 ms 276692 KB Output is correct
39 Correct 2952 ms 276868 KB Output is correct
40 Correct 2672 ms 234876 KB Output is correct
41 Correct 2983 ms 321672 KB Output is correct
42 Correct 3296 ms 324516 KB Output is correct
43 Correct 3329 ms 324304 KB Output is correct
44 Correct 3063 ms 276296 KB Output is correct