oj.uz

Submission #634563

# Submission time Handle Problem Language Result Execution time Memory
634563 2022-08-24T14:59:24 Z yunny_world NLO (COCI18_nlo) C++14
44 / 110
 834 ms 328 KB 
#include <bits/stdc++.h>
#define ll long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define X first
#define Y second
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

ll n, m, k;
tuple<ll, ll, ll> query[105];
int ans;

void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        ll x, y, r; cin>>x>>y>>r;
        query[i]=tie(x, y, r);
    }

    ans=n*m*k;

    for(int i=1;i<=m;i++)
    {
        vector<pll> v;

        for(int j=1;j<=k;j++)
        {
            ll x, y, r;
            tie(x, y, r)=query[j];

            ll s=x-floor(sqrt(r*r-(y-i)*(y-i)));
            ll e=x+floor(sqrt(r*r-(y-i)*(y-i)));
            if(s>0 && e>0 && s<=e)
            {
                v.push_back({s, j});
                v.push_back({e+1, -j});
            }
        }

        sort(v.begin(), v.end());

        set<ll> s;
        for(int j=0;j<v.size();j++)
        {
            //cout<<v[j].X<<' '<<v[j].Y<<'\n';
            if(!s.empty()) ans-=(*s.rbegin() * (v[j].X-v[j-1].X));
            if(v[j].Y<0) s.erase(-v[j].Y);
            else s.insert(v[j].Y);
        }
        //cout<<'\n';
    }
    cout<<ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1; //cin >> tc;
    while (tc--) solve();
    return 0;
}
/*
어떤 위치에 q번째 쿼리가 마지막으로 적용 됨 -> k-q 만큼의 풀이 자람
즉, 각 위치에 대해 가장 마지막으로 적용된 쿼리만 알면 된다.
*/

Compilation message

nlo.cpp: In function 'void solve()':
nlo.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int j=0;j<v.size();j++)
      |                     ~^~~~~~~~~

Subtask #1
44.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct
2 Correct 12 ms 328 KB Output is correct
3 Correct 8 ms 324 KB Output is correct
4 Correct 63 ms 308 KB Output is correct
5 Incorrect 68 ms 304 KB Output isn't correct
6 Incorrect 383 ms 316 KB Output isn't correct
7 Incorrect 161 ms 308 KB Output isn't correct
8 Incorrect 626 ms 316 KB Output isn't correct
9 Incorrect 231 ms 300 KB Output isn't correct
10 Incorrect 834 ms 320 KB Output isn't correct