제출 #1049836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049836		vjudge1	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	344 KiB

art

#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
#define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int N = 500100;
int t[N*4];
void build (vector <int> a, int v, int tl, int tr) {
	if (tl == tr)
		t[v] = a[tl];
	else {
		int tm = (tl + tr) / 2;
		build (a, v*2, tl, tm);
		build (a, v*2+1, tm+1, tr);
		t[v] = max(t[v*2], t[v*2+1]);
	}
}
int sum (int v, int tl, int tr, int l, int r) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	return max(sum (v*2, tl, tm, l, min(r,tm))
		, sum (v*2+1, tm+1, tr, max(l,tm+1), r));
}
void solve() {
    int n;
    cin>>n;
    vii a(n);
    for(int i=0; i<n; i++){
    	cin>>a[i].f>>a[i].s;
    }
    
    sort(all(a));
    for(int i=0; i<a.size()-1; i++){
    	if(a[i].f==a[i+1].f){
    		a[i+1].s+=a[i].s;
    		a.erase(a.begin()+i);
    		i--;
    	}
    }
    n=a.size();
    // for(int i=0; i<n; i++){
    	// cout<<a[i].f<<" "<<a[i].s<<en;	
    // }
    
    vi p(n+1, 0), pl(n+1, 0), pr(n+1, 0);
    for(int i=0; i<n; i++){
    	p[i+1] = p[i] + a[i].s;
    }
    for(int i=1; i<=n; i++){
    	pl[i] = a[i-1].f - p[i-1];
    }
    for(int i=1; i<=n; i++){
    	pr[i] = p[i] - a[i-1].f;
    }
    // for(int i=0; i<n; i++){
    	// cout<<a[i].f<<" "<<a[i].s<<" "<<p[i+1]<<" "<<pl[i+1]<<" "<<pr[i+1]<<en;
    // }
    build(pl, 1, 0, n);
    int mx1=0, mx2=0;
    int ans=0;
    for(int i=0; i<=n; i++){
    	ans=max(ans, sum(1, 0, n, 0, i-1) + pr[i]);
    }
    cout<<ans;
    
}

signed main() {
    fast_io;
    int tc = 1;
    // scanf("%d", &tc);
    while (tc--)
        solve();
}

컴파일 시 표준 에러 (stderr) 메시지

art.cpp: In function 'void solve()':
art.cpp:47:19: 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]
   47 |     for(int i=0; i<a.size()-1; i++){
      |                  ~^~~~~~~~~~~
art.cpp:73:9: warning: unused variable 'mx1' [-Wunused-variable]
   73 |     int mx1=0, mx2=0;
      |         ^~~
art.cpp:73:16: warning: unused variable 'mx2' [-Wunused-variable]
   73 |     int mx1=0, mx2=0;
      |                ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50