Submission #146088

#	Time	Username	Problem	Language	Result	Execution time	Memory
146088		mhy908	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	121 ms	28876 KiB

bridge

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
LL temp, ans=987654321987654321;
int n, re, k;
LL arr[200010];
struct SEGMENT_TREE {
    struct NODE {
        int st, fin, len;
        long long sum, maxx, minn;
        long long lazy;
    } tree[3000000];
    const long long inf=987654321987654321;
    int x;
    void relaxnode(int point){
        tree[point].maxx=max(tree[point*2].maxx+tree[point*2].lazy, tree[point*2+1].maxx+tree[point*2+1].lazy);
        tree[point].minn=min(tree[point*2].minn+tree[point*2].lazy, tree[point*2+1].minn+tree[point*2+1].lazy);
        tree[point].sum=tree[point*2].sum+tree[point*2].lazy*tree[point*2].len+tree[point*2+1].sum+tree[point*2+1].lazy*tree[point*2+1].len;
    }
    void maketree(int point, int num) {
        if(num==1) {
            x++;
            tree[point].st=tree[point].fin=x;
            tree[point].len=1;
        }
        if(num<=1)
            return;
        maketree(point*2, num-num/2);
        maketree(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
        tree[point].len=tree[point*2].len+tree[point*2+1].len;
    }
    long long sumrange(int a, int b, int point) {
        if(tree[point].st==tree[point].fin) {
            tree[point].maxx+=tree[point].lazy;
            tree[point].minn+=tree[point].lazy;
            tree[point].sum+=tree[point].lazy*tree[point].len;
            tree[point].lazy=0;
        }
        if(tree[point].st>=a&&tree[point].fin<=b)
            return tree[point].sum+tree[point].lazy*tree[point].len;
        if(tree[point].st>b||tree[point].fin<a)
            return 0;
        tree[point*2].lazy+=tree[point].lazy;
        tree[point*2+1].lazy+=tree[point].lazy;
        tree[point].lazy=0;
        LL ret=sumrange(a, b, point*2)+sumrange(a, b, point*2+1);
        relaxnode(point);
        return ret;
    }
    long long maxrange(int a, int b, int point) {
        if(tree[point].st==tree[point].fin) {
            tree[point].maxx+=tree[point].lazy;
            tree[point].minn+=tree[point].lazy;
            tree[point].sum+=tree[point].lazy*tree[point].len;
            tree[point].lazy=0;
        }
        if(tree[point].st>=a&&tree[point].fin<=b)
            return tree[point].maxx+tree[point].lazy;
        if(tree[point].st>b||tree[point].fin<a)
            return -inf;
        tree[point*2].lazy+=tree[point].lazy;
        tree[point*2+1].lazy+=tree[point].lazy;
        tree[point].lazy=0;
        LL ret=max(maxrange(a, b, point*2), maxrange(a, b, point*2+1));
        relaxnode(point);
        return ret;
    }
    long long minrange(int a, int b, int point) {
        if(tree[point].st==tree[point].fin) {
            tree[point].maxx+=tree[point].lazy;
            tree[point].minn+=tree[point].lazy;
            tree[point].sum+=tree[point].lazy*tree[point].len;
            tree[point].lazy=0;
        }
        if(tree[point].st>=a&&tree[point].fin<=b)
            return tree[point].minn+tree[point].lazy;
        if(tree[point].st>b||tree[point].fin<a)
            return inf;
        tree[point*2].lazy+=tree[point].lazy;
        tree[point*2+1].lazy+=tree[point].lazy;
        tree[point].lazy=0;
        LL ret=min(minrange(a, b, point*2), minrange(a, b, point*2+1));
        relaxnode(point);
        return ret;
    }
    void updaterange(int point, int num, long long p) {
        if(tree[point].st==tree[point].fin) {
            tree[point].sum=tree[point].maxx=tree[point].minn=p;
            tree[point].lazy=0;
            return;
        }
        tree[point*2].lazy+=tree[point].lazy;
        tree[point*2+1].lazy+=tree[point].lazy;
        tree[point].lazy=0;
        if(num<=tree[point*2].fin)
            updaterange(point*2, num, p);
        else
            updaterange(point*2+1, num, p);
        relaxnode(point);
    }
    void alterrange(int point, int a, int b, long long p) {
        if(tree[point].fin<a||tree[point].st>b)
            return;
        if(tree[point].st>=a&&tree[point].fin<=b) {
            if(tree[point].st==tree[point].fin) {
                tree[point].maxx+=tree[point].lazy;
                tree[point].minn+=tree[point].lazy;
                tree[point].sum+=tree[point].lazy*tree[point].len;
                tree[point].lazy=0;
            }
            tree[point].lazy+=p;
            return;
        }
        tree[point*2].lazy+=tree[point].lazy;
        tree[point*2+1].lazy+=tree[point].lazy;
        tree[point].lazy=0;
        alterrange(point*2, a, b, p);
        alterrange(point*2+1, a, b, p);
        relaxnode(point);
    }
    void init(int n) {
        maketree(1, n);
    }
    long long get_sum(int a, int b) {
        return sumrange(a, b, 1);
    }
    long long get_min(int a, int b) {
        return minrange(a, b, 1);
    }
    long long get_max(int a, int b) {
        return maxrange(a, b, 1);
    }
    void update(int a, long long num) {
        updaterange(1, a, num);
    }
    void alter(int a, int b, long long num) {
        alterrange(1, a, b, num);
    }
}seg;
int main()
{
    scanf("%d %d", &k, &n);
    for(int i=1; i<=n; i++){
        char a, b;
        LL c, d;
        scanf(" %c %lld %c %lld", &a, &c, &b, &d);
        if(a==b)temp+=llabs(c-d);
        else{
            arr[++re]=c;
            arr[++re]=d;
        }
    }
    sort(arr+1, arr+re+1);
    seg.init(re);
    for(int i=1; i<=re; i++){
        seg.update(i, arr[i]);
    }
    if(k==1){
        ans=seg.get_sum(re/2+1, re);
        ans-=seg.get_sum(1, re/2);
        printf("%lld", ans+temp+(LL)re/2);
        return 0;
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:153:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %lld %c %lld", &a, &c, &b, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37