Submission #92798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92798	2019-01-04T21:34:32 Z	fbosnjak	NLO (COCI18_nlo)	C++14	88 / 110	551 ms	66560 KB

nlo

#include <bits/stdc++.h>
using namespace std;

int n, m, k, x, y, r;
long long sol, val, mid, pl;
vector <pair <int,int> > v[100100];

class cmp
{
public:
    bool operator ()(pair <int,int> a, pair <int,int> b) {
        if (a.second!=b.second) return a.second>b.second;
        return a.first<b.first;
    }
};

void sweep(int x)
{
    long long sol1=sol;
    set <pair <int,int>, cmp> s;
    set <pair <int,int>, cmp>::iterator it;
    bool aktiv=0;
    int last=v[x][0].first;
    s.insert(v[x][0]);
    if (v[x][0].second==0) aktiv=1;
    for (int i=1;i<v[x].size();i++) {
        if (aktiv) {
            it=s.begin();
            sol+=(long long)((v[x][i].first-last)*(k-it->second));
        }
        if (v[x][i].second==0) {
            if (aktiv) {
                aktiv=0;
                s.erase(make_pair(1,0));
            }
            else {
                aktiv=1;
                s.insert(make_pair(1,0));
            }
        }
        else {
            if (v[x][i].second<0) s.erase(s.lower_bound(make_pair(-1e9,-v[x][i].second)));
            else s.insert(v[x][i]);
        }
        last=v[x][i].first;
    }
}

int bs(int x, int lou, int haj)
{
    while (haj-lou>1) {
        int mid=(lou+haj)/2;
        if (pl+(y-mid)*(y-mid)<=val) haj=mid;
        else lou=mid;
    }
    if ((y-lou)*(y-lou)+pl<=val) return lou;
    else return haj;
}

int bs2(int x, int lou, int haj)
{
    while (haj-lou>1) {
        int mid=(lou+haj)/2;
        if (pl+(y-mid)*(y-mid)<=val) lou=mid;
        else haj=mid;
    }
    if ((y-haj)*(y-haj)+pl<=val) return haj;
    else return lou;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();

    cin >> n >> m >> k;
    for (int i=1;i<=k;i++) {
        cin >> x >> y >> r;
        for (int j=max(1,x-r);j<=min(n,x+r);j++) {
            pl=(x-j)*(x-j);
            val=(long long)r*r;
            v[j].push_back(make_pair(bs(j,0,y),i));
            v[j].push_back(make_pair(bs2(j,y,m+1)+1,-i));
        }
    }
    for (int i=1;i<=n;i++) {v[i].push_back(make_pair(1,0)); v[i].push_back(make_pair(m+1,0));}

    for (int i=1;i<=n;i++) {
        sort(v[i].begin(),v[i].end());
    }

    for (int i=1;i<=n;i++) sweep(i);

    cout << sol;

}

Compilation message

nlo.cpp: In function 'void sweep(int)':
nlo.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<v[x].size();i++) {
                  ~^~~~~~~~~~~~
nlo.cpp:19:15: warning: unused variable 'sol1' [-Wunused-variable]
     long long sol1=sol;
               ^~~~

Subtask #1

88.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3064 KB	Output is correct
2	Correct	18 ms	3832 KB	Output is correct
3	Correct	14 ms	3832 KB	Output is correct
4	Correct	91 ms	9464 KB	Output is correct
5	Correct	72 ms	8568 KB	Output is correct
6	Correct	551 ms	49460 KB	Output is correct
7	Correct	227 ms	21624 KB	Output is correct
8	Runtime error	528 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Correct	403 ms	36280 KB	Output is correct
10	Runtime error	551 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)