Submission #131119

#	Time	Username	Problem	Language	Result	Execution time	Memory
131119		tjdgus4384	수족관 2 (KOI13_aqua2)	C++14	0 / 100	943 ms	68000 KiB

aqua2

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[500001];
int seg[2000001], seg1, lefted;
int h1[500001];
int n, x1[300001], y2[300001], k, a, b, c, d;

void update(int left, int right, int node, int start, int end){
    if(left >= end || right <= start) return;
    seg[node]++;
    int mid = (left+right)/2;
    if(mid == left || mid == right) return;
    update(left, mid, node*2, start, end);
    update(mid, right, node*2+1, start, end);
}
int get(int left, int right, int node, int start, int end){
    if(left >= end || right <= start) return 0;
    if(right <= end && left >= start) return seg[node];
    if(left < start || right > end){
        int mid = (left+right)/2;
        int ans = max(get(left, mid, node*2, start, end) , get(mid, right, node*2+1, start, end));
    }
}

double solve(int x, int y, int h){
    if(x >= y) return 0;
    double ans = 0;
    int k = get(0, seg1, 1, x, y);
    if(k == 0){
        for(int i = x;i < y;i++){
            lefted += h1[i] - h;
        }
        return 0;
    }
    bool chk = false;
    for(int i = 0;i < v[h].size();i++){
        if(v[h][i].first >= x && v[h][i].second <= y){
            ans += solve(x, v[h][i].first, h);
            x = v[h][i].second;
            chk = true;
        }
    }
    if(chk) ans += solve(x, y, h);
    else ans = solve(x, y, h + 1) + (y - x) / k;
    return ans;
}

int main(){
    scanf("%d", &n);
    for(int i = 0;i < n;i++){
        scanf("%d %d", &x1[i], &y2[i]);
        if(i == 0) continue;
        if(y2[i] == y2[i - 1]){
            bool chk = false;
            if(x1[i - 1] > x1[i]) {swap(x1[i - 1], x1[i]);chk = true;}
            v[y2[i]].push_back({x1[i - 1], x1[i]});
            for(int j = x1[i - 1];j < x1[i];j++) h1[j] = y2[i];
            if(chk) swap(x1[i - 1], x1[i]);
        }
    }
    seg1 = x1[n - 1];
    scanf("%d", &k);
    for(int i = 0;i < k;i++){
        scanf("%d %d %d %d", &a, &b, &c, &d);
        update(0, x1[n - 1], 1, a, c);
    }
    printf("%.2lf\n", solve(0, x1[n - 1], 0));
    printf("%d", lefted);
    return 0;
}

Compilation message (stderr)

aqua2.cpp: In function 'int get(int, int, int, int, int)':
aqua2.cpp:21:13: warning: unused variable 'ans' [-Wunused-variable]
         int ans = max(get(left, mid, node*2, start, end) , get(mid, right, node*2+1, start, end));
             ^~~
aqua2.cpp: In function 'double solve(int, int, int)':
aqua2.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < v[h].size();i++){
                   ~~^~~~~~~~~~~~~
aqua2.cpp: In function 'int get(int, int, int, int, int)':
aqua2.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
aqua2.cpp: In function 'int main()':
aqua2.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
aqua2.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x1[i], &y2[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
aqua2.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a, &b, &c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 35
• Subtask 4: 0 / 31