oj.uz

Submission #205563

# Submission time Handle Problem Language Result Execution time Memory
205563 2020-02-29T08:09:44 Z jh05013 None (JOI14_ho_t5) C++17
20 / 100
 160 ms 9868 KB 
#include <bits/stdc++.h>
#define sz(X) (int)((X).size())
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);}
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;}
 
template <typename T>
struct Compress{
    int n; vector<T> arr;
    void add(T x){arr.push_back(x); n++;}
    void init(){sort(entire(arr)), 
        arr.erase(unique(entire(arr)), arr.end()), n=arr.size();}
    int lb(T x){return lower_bound(entire(arr), x) - arr.begin();}
};
 
template <typename T>
struct Fenwick{
    int n; vector<T> arr;
    Fenwick(int N): n{N}, arr(N) {}
    void add(int i, T val){
        while(i < n) arr[i]+= val, i |= i+1;
    }
    T getsum(int i){
        T res = 0;
        while(i >= 0) res+= arr[i], i = (i&(i+1))-1;
        return res;
    }
    T intersum(int i, int j){
        if(j < i) return 0;
        return i? (getsum(j) - getsum(i-1)) : getsum(j);
    }
};
 
int main(){OJize();
    int w,h,n; cin>>w>>h>>n;
    vector<tuple<int,int,int,int>> ev; // y, type, l, r
    Compress<int> C;
    C.add(0), C.add(w);
    // type 1 = vertical start (uses l=r)
    // type 2 = horizontal (uses l, r)
    // type 3 = vertical end (uses l=r)
    for(int i=0; i<n; i++){
        int xa,ya,xb,yb; cin>>xa>>ya>>xb>>yb;
        C.add(xa), C.add(xb);
        if(xa == xb){
            ev.push_back({ya, 1, xa, xb});
            ev.push_back({yb, 3, xa, xb});
        }
        else ev.push_back({ya, 2, xa, xb});
    }
    ev.push_back({0,2,0,w}), ev.push_back({h,2,0,w});
    ev.push_back({0,1,0,0}), ev.push_back({0,1,w,w});
    ev.push_back({h,3,0,0}), ev.push_back({h,3,w,w});
    C.init(), sort(entire(ev));
    Fenwick<int> F(sz(C.arr));
 
    // count V and E
    ll V=0, E=0, COMP=0;
    for(auto [y,ty,x1,x2]: ev){
        x1 = C.lb(x1), x2 = C.lb(x2);
        if(ty == 1){
            F.add(x1, 1);
            V++;
        }
        else if(ty == 2){
            // how many intersections inside the bar?
            ll ic = F.intersum(x1, x2);
            V+= ic+2;
            E+= 2*ic+1;
        }
        else if(ty == 3){
            F.add(x1, -1);
            V++; E++;
        }
        //cout<<y<<' '<<ty<<' '<<x1<<' '<<x2<<' '<<V<<endl;
    }
    COMP = 1; // subtask 4
 
    cout << E-V+COMP;
}

Compilation message

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:61:25: warning: unused variable 'y' [-Wunused-variable]
     for(auto [y,ty,x1,x2]: ev){
                         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 17 ms 1144 KB Output is correct
4 Correct 6 ms 296 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 160 ms 9868 KB Output is correct
7 Correct 14 ms 1144 KB Output is correct
8 Correct 105 ms 9064 KB Output is correct
9 Correct 112 ms 9064 KB Output is correct
10 Correct 110 ms 9064 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -