제출 #219773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219773		_7_7_	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	272 ms	33528 KiB

constellation3

#include <bits/stdc++.h>

#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")


#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first


using namespace std;


typedef pair < long long, long long > pll;
typedef pair < int, int > pii;
typedef unsigned long long ull;
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;
typedef long long ll;
typedef double db;


const int inf = 1e9, maxn = 4e5 + 148, mod = 777777777, N = 2e5 + 61;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 455;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int t[N], n, h, x, y, z, m, p[N], l[N], r[N], dp[N], sum;
bool was[N];
vpii gg[N];
vi g[N];

void inc (int pos, int x) {
    while (pos < N) {
        t[pos] += x;
        pos |= pos + 1;
    }
}

int Get (int r) {
    int res = 0;
    while (r >= 0) {
        res += t[r];
        r = (r & (r + 1)) - 1;
    }
    return res;
}

int update (int l, int r, int x) {
    inc(l, x);
    inc(r + 1, -x);
}

int get (int v) {
    return v == p[v] ? v : p[v] = get(p[v]);
}

void merge (int v, int u) {
    v = get(v);
    u = get(u);

    if (r[u] - l[u] > r[v] - l[u])
        swap(v, u);

//    cerr << " + " << l[v] << ' ' << r[v] << ' ' << dp[u] << endl;
//    cerr << " + " << l[u] << ' ' << r[u] << ' ' << dp[v] << endl;
    update(l[v], r[v], dp[u]);
    update(l[u], r[u], dp[v]);
	
	p[u] = v;
    dp[v] += dp[u];
    l[v] = min(l[v], l[u]);
    r[v] = max(r[v], r[u]);
}




main () {
//    file("");
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &h);
        g[h].pb(i);
    }

    for (int i = 1; i <= n; ++i)
        l[i] = r[i] = p[i] = i;

    scanf("%lld", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%lld%lld%lld", &x, &y, &z);
        gg[y].pb({x, z});
        sum += z;
    }

    for (int j = 1; j <= n; ++j) {
        for (auto i : gg[j]) 
            dp[get(i.f)] = max(dp[get(i.f)], Get(i.f) + i.s);
       

        for (auto i : g[j]) {
            was[i] = 1;
            if (was[i - 1])
                merge(i - 1, i);
            if (was[i + 1])
                merge(i + 1, i);
        }

/*		for (int i = 1; i <= n; ++i)
			if (i == get(i))
				cout << i << ' ' << dp[i] << endl;
		cout << endl;                             */
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, dp[i]);    


    cout << sum - ans << endl;
}

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

constellation3.cpp: In function 'long long int update(long long int, long long int, long long int)':
constellation3.cpp:63:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
constellation3.cpp: At global scope:
constellation3.cpp:90:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
constellation3.cpp: In function 'int main()':
constellation3.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
constellation3.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &h);
         ~~~~~^~~~~~~~~~~~
constellation3.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &m);
     ~~~~~^~~~~~~~~~~~
constellation3.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65