Submission #92145

#	Time	Username	Problem	Language	Result	Execution time	Memory
92145		Kastanda	Sunčanje (COCI18_suncanje)	C++11	130 / 130	1705 ms	154452 KiB

suncanje

#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 (stderr)

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 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13