oj.uz

Submission #92145

# Submission time Handle Problem Language Result Execution time Memory
92145 2019-01-01T16:44:22 Z Kastanda Sunčanje (COCI18_suncanje) C++11
130 / 130
 1705 ms 154452 KB 
#include<bits/stdc++.h>
#define spii set<pair<int,int>>
using namespace std;
const int N = 100005;
int n, X[N], Y[N], A[N], B[N];
bool M[N];
vector < int > U;
spii S[N * 8][2];
inline spii::iterator Left(spii &F, int l)
{
    auto it = F.lower_bound({l, -1});
    if (it != F.begin())
    {
        it --;
        if (it->second >= l)
            return (it);
        it ++;
    }
    return (it);
}
inline spii::iterator Right(spii &F, int r)
{
    return (F.lower_bound({r, -1}));
}
inline bool Get(spii &F, int l, int r)
{
    return (Left(F, l) != Right(F, r));
}
inline void Add(spii &F, int l, int r)
{
    int nl = l, nr = r;
    auto le = Left(F, l), ri = Right(F, r);
    if (le != ri)
    {
        ri --;
        nl = min(nl, le->first);
        nr = max(nr, ri->second);
        ri ++; F.erase(le, ri);
    }
    F.insert({nl, nr});
}
bool Add(int le, int ri, int st, int en, int id = 1, int l = 0, int r = U.size())
{
    if (ri <= l || r <= le)
        return (0);
    if (le <= l && r <= ri)
    {
        bool w = Get(S[id][0], st, en) | Get(S[id][1], st, en);
        Add(S[id][0], st, en); return (w);
    }
    Add(S[id][1], st, en); bool w = 0;
    w |= Add(le, ri, st, en, id << 1, l, (l + r) >> 1);
    w |= Add(le, ri, st, en, id << 1 ^ 1, (l + r) >> 1, r);
    return (w | Get(S[id][0], st, en));
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d%d", &X[i], &Y[i], &A[i], &B[i]),
        U.push_back(X[i]), U.push_back(X[i] + A[i]);
    sort(U.begin(), U.end());
    U.resize(unique(U.begin(), U.end()) - U.begin());
    for (int i = n; i; i--)
    {
        int le = lower_bound(U.begin(), U.end(), X[i]) - U.begin();
        int ri = lower_bound(U.begin(), U.end(), X[i] + A[i]) - U.begin();
        M[i] = Add(le, ri, Y[i], Y[i] + B[i]);
    }
    for (int i = 1; i <= n; i++)
        puts(M[i] ? "NE" : "DA");
    return (0);
}

Compilation message

suncanje.cpp: In function 'int main()':
suncanje.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
suncanje.cpp:61:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &X[i], &Y[i], &A[i], &B[i]),
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         U.push_back(X[i]), U.push_back(X[i] + A[i]);
         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 78200 KB Output is correct
2 Correct 117 ms 79352 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 82040 KB Output is correct
2 Correct 767 ms 107584 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 86968 KB Output is correct
2 Correct 988 ms 118000 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 92160 KB Output is correct
2 Correct 727 ms 111444 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 107408 KB Output is correct
2 Correct 1027 ms 118484 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 104904 KB Output is correct
2 Correct 924 ms 118932 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 114348 KB Output is correct
2 Correct 1000 ms 109124 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1506 ms 134208 KB Output is correct
2 Correct 758 ms 104048 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1439 ms 131932 KB Output is correct
2 Correct 1531 ms 138728 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1346 ms 134952 KB Output is correct
2 Correct 1705 ms 154452 KB Output is correct