Submission #96316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
96316	2019-02-08T11:18:40 Z	kraljlavova1	NLO (COCI18_nlo)	C++11	88 / 110	354 ms	66560 KB

nlo

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
const int MAX = 1e5 + 10;
struct seg{
	int s;
	int e;
	int t;
};
int n, m;
int k;
vector<seg> ls[MAX];
ll sol, sum, lsum;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin >> n >> m;
	cin >> k;
	for(int i = 1;i <= n; i++){
		ls[i].push_back({1, m, 0});
	}
	for(int i = 1;i <= k; i++){
		int x, y, r;
		cin >> x >> y >> r;
		for(int j = x - r;j <= x + r; j++){
			ll tmp = r * r - (j - x) * (j - x), ntmp;
			tmp = sqrt(tmp);
			ntmp = -tmp;
			ls[j].push_back({(int)ntmp + y, (int)tmp + y, i});
		}
	}
	//
	//ll tsum = 0;
	for(int i = 1;i <= n; i++){
		vector<seg> vs;
		for(int j = ls[i].size() - 1;j >= 0; j--){
			vector<seg> c;
			c.push_back(ls[i][j]);
			for(int y = 0;y < c.size(); y++){
				//cout << "obradi " << c[y].s << " " << c[y].e << " " << c[y].t << "\n";
				for(int x = 0;x < vs.size(); x++){
					if(c[y].e < vs[x].s || c[y].s > vs[x].e) continue;
					if(c[y].s < vs[x].s && c[y].e <= vs[x].e){
						c[y].e = vs[x].s - 1;
					}
					else if(c[y].s >= vs[x].s && c[y].e > vs[x].e){
						c[y].s = vs[x].e + 1;
					}
					else if(c[y].s >= vs[x].s && c[y].e <= vs[x].e){
						c.erase(c.begin() + y);
						y--;
						break;
					}
					else{
						c.push_back({c[y].s, vs[x].s - 1, ls[i][j].t});
						c.push_back({vs[x].e + 1, c[y].e, ls[i][j].t});
						c.erase(c.begin() + y);
						y--;
						break;
					}
				}
			}
			sum = 0;
			for(int y = 0;y < c.size(); y++){
				//cout << "i s e : " << i << " " << c[y].s << " " << c[y].e << "\n";
				sum += c[y].e - c[y].s + 1;
				vs.push_back(c[y]);
			}
			//if(k - ls[i][j].t  == 0) cout << "i sum k ls[i][j].t dif : " << i << " " << sum << " " << k << " " << ls[i][j].t << " " << k - ls[i][j].t << "\n";
			//if(k - ls[i][j].t == 0) tsum += sum;
			sol += sum * (k - ls[i][j].t);
		}
	}
	//cout << n * m - tsum << "\n";
	cout << sol << "\n";
	return 0;
}

Compilation message

nlo.cpp: In function 'int main()':
nlo.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int y = 0;y < c.size(); y++){
                  ~~^~~~~~~~~~
nlo.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int x = 0;x < vs.size(); x++){
                   ~~^~~~~~~~~~~
nlo.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int y = 0;y < c.size(); y++){
                  ~~^~~~~~~~~~

Subtask #1

88.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2936 KB	Output is correct
2	Correct	9 ms	3576 KB	Output is correct
3	Correct	11 ms	3576 KB	Output is correct
4	Correct	41 ms	7800 KB	Output is correct
5	Correct	51 ms	7160 KB	Output is correct
6	Correct	283 ms	38008 KB	Output is correct
7	Correct	107 ms	17144 KB	Output is correct
8	Runtime error	265 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Correct	231 ms	28408 KB	Output is correct
10	Runtime error	354 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)