| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 400176 |
2021-05-07T13:39:12 Z |
mathking1021 |
None (KOI17_cut) |
C++17 |
|
1 ms |
332 KB |
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define PLL pair<ll, ll>
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll INF = 4e18;
ll n;
ll a[1000005];
ll b[1000005];
vector<ll> ve1, ve2;
vector<PLL> ve;
stack<ll> st1, st2, st3;
ll ans1, ans2;
int main()
{
scanf("%lld", &n);
for(ll i = 0; i < n; i++)
{
scanf("%lld%lld", &a[i], &b[i]);
}
for(ll i = 1; i <= n; i++)
{
if(b[i - 1] < 0 && b[i % n] > 0) ve1.push_back(a[i]);
else if(b[i - 1] > 0 && b[i % n] < 0)
{
if(ve1.empty()) ve1.push_back(INF);
ve2.push_back(a[i % n]);
}
}
if(ve1[0] == INF) ve1[0] = ve1.back(), ve1.pop_back();
for(ll i = 0; i < ve1.size(); i++)
{
ve.push_back(make_pair(ve1[i], ve2[i]));
}
for(ll i = 0; i < ve.size(); i++)
{
if(ve[i].F > ve[i].S) swap(ve[i].F, ve[i].S);
}
sort(ve.begin(), ve.end());
for(ll i = 0; i < ve.size(); i++)
{
while(!st1.empty() && st2.top() < ve[i].F)
{
if(st3.top() == 0) ans1++;
st1.pop(), st2.pop(), st3.pop();
}
if(!st3.empty())
{
st3.pop(), st3.push(1);
}
st1.push(ve[i].F), st2.push(ve[i].S), st3.push(0);
}
while(!st1.empty())
{
if(st3.top() == 0) ans1++;
st1.pop(), st2.pop(), st3.pop();
}
for(ll i = 0; i < ve.size(); i++)
{
while(!st1.empty() && st2.top() < ve[i].F)
{
if(st3.top() == 0) ans2++;
st1.pop(), st2.pop(), st3.pop();
}
if(!st3.empty())
{
st1.push(ve[i].F), st2.push(ve[i].S), st3.push(1);
}
else
{
st1.push(ve[i].F), st2.push(ve[i].S), st3.push(0);
}
}
while(!st1.empty())
{
if(st3.top() == 0) ans2++;
st1.pop(), st2.pop(), st3.pop();
}
printf("%lld %lld\n", ans2, ans1);
return 0;
}
Compilation message
cut.cpp: In function 'int main()':
cut.cpp:41:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(ll i = 0; i < ve1.size(); i++)
| ~~^~~~~~~~~~~~
cut.cpp:45:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(ll i = 0; i < ve.size(); i++)
| ~~^~~~~~~~~~~
cut.cpp:50:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(ll i = 0; i < ve.size(); i++)
| ~~^~~~~~~~~~~
cut.cpp:68:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(ll i = 0; i < ve.size(); i++)
| ~~^~~~~~~~~~~
cut.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
26 | scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
cut.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
29 | scanf("%lld%lld", &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
