oj.uz

답안 #131119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131119 2019-07-16T14:37:16 Z tjdgus4384 수족관 2 (KOI13_aqua2) C++14
0 / 100
 943 ms 68000 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12280 KB Output is correct
2 Incorrect 13 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 123 ms 44304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 943 ms 68000 KB Output isn't correct
2 Halted 0 ms 0 KB -