oj.uz

Submission #141356

# Submission time Handle Problem Language Result Execution time Memory
141356 2019-08-07T13:38:37 Z meatrow Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 1635 ms 243432 KB 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

/** Interface */
 
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );
 
/** Read */
 
static const int buf_size = 4096;
 
inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}
 
inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}
 
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
 
/** Write */
 
static int write_pos = 0;
static char write_buf[buf_size];
 
inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
 
template <class T>
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;
 
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
 
inline void writeWord( const char *s ) {
    while (*s)
        writeChar(*s++);
}
 
struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;

const int N = 1e8;

pair<int,  int> a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n = readInt();
    for (int i = 0; i < n; i++) {
        int x = readInt();
        int y = readInt();
        a[i] = { x + y, x - y };
    }
    sort(a, a + n, [](auto& a, auto& b) {
        return a.first > b.first || a.first == b.first && a.second < b.second;
    });
    int ans = 0;
    int y = INT32_MAX;
    for (int i = 0; i < n; i++) {
        if (a[i].second < y) {
            ans++;
        }
        y = min(y, a[i].second);
    }
    writeInt(ans);
    return 0;
}

Compilation message

lightningrod.cpp: In instantiation of 'main()::<lambda(auto:1&, auto:2&)> [with auto:1 = std::pair<int, int>; auto:2 = std::pair<int, int>]':
/usr/include/c++/7/bits/predefined_ops.h:143:18:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = std::pair<int, int>*; _Iterator2 = std::pair<int, int>*; _Compare = main()::<lambda(auto:1&, auto:2&)>]'
/usr/include/c++/7/bits/stl_algo.h:81:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = std::pair<int, int>*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1&, auto:2&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1921:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::pair<int, int>*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1&, auto:2&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1953:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = std::pair<int, int>*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1&, auto:2&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1968:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::pair<int, int>*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:1&, auto:2&)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = std::pair<int, int>*; _Compare = main()::<lambda(auto:1&, auto:2&)>]'
lightningrod.cpp:105:6:   required from here
lightningrod.cpp:104:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return a.first > b.first || a.first == b.first && a.second < b.second;
                                     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 87032 KB Output is correct
2 Correct 509 ms 188352 KB Output is correct
3 Correct 523 ms 183180 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 30 ms 5404 KB Output is correct
15 Correct 24 ms 5296 KB Output is correct
16 Correct 17 ms 4600 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 91040 KB Output is correct
2 Correct 594 ms 174216 KB Output is correct
3 Correct 586 ms 169880 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 87032 KB Output is correct
2 Correct 509 ms 188352 KB Output is correct
3 Correct 523 ms 183180 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 30 ms 5404 KB Output is correct
18 Correct 24 ms 5296 KB Output is correct
19 Correct 17 ms 4600 KB Output is correct
20 Correct 575 ms 91040 KB Output is correct
21 Correct 594 ms 174216 KB Output is correct
22 Correct 586 ms 169880 KB Output is correct
23 Correct 1635 ms 243432 KB Output is correct
24 Correct 1315 ms 225588 KB Output is correct
25 Correct 962 ms 207324 KB Output is correct