| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 989782 |
2024-05-28T19:08:24 Z |
PedroBigMan |
Sails (IOI07_sails) |
C++14 |
|
249 ms |
13648 KB |
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class ST
{
public:
ll N;
class SV //seg value
{
public:
ll a;
SV() {a=0LL;}
SV(ll x) {a=x;}
SV operator & (SV X) {SV ANS(a+X.a); return ANS;}
};
class LV //lazy value
{
public:
ll a;
LV() {a=0LL;}
LV(ll x) {a=x;}
LV operator & (LV X) {LV ANS(a+X.a); return ANS;}
};
SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node
{
SV X(p[c].a+(range[c].ss-range[c].ff+1)*lazy[c].a);
return X;
}
SV neuts; LV neutl;
vector<SV> p;
vector<LV> lazy;
vector<pl> range;
ST() {N=0LL;}
ST(vector<ll> arr)
{
N = (ll) 1<<(ll) ceil(log2(arr.size()));
REP(i,0,2*N) {range.pb(mp(0LL,0LL));}
REP(i,0,N) {p.pb(neuts);}
REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);}
REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);}
ll cur = N-1;
while(cur>0)
{
p[cur]=p[2*cur]&p[2*cur+1];
range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss);
cur--;
}
REP(i,0,2*N) {lazy.pb(neutl);}
}
void prop(ll c) //how lazy values propagate
{
p[c] = upval(c);
lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1];
lazy[c]=neutl;
}
SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b)
{
if(a>b) {return neuts;}
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return neuts;}
if(x>=a && y<=b) {return upval(c);}
prop(c);
SV ans = query(a,b,2*c)&query(a,b,2*c+1);
return ans;
}
void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b)
{
if(a>b) {return;}
ll x=range[c].ff; ll y=range[c].ss;
if(y<a || x>b) {return ;}
if(x>=a && y<=b)
{
lazy[c]=s&lazy[c];
return;
}
prop(c);
update(s,a,b,2*c); update(s,a,b,2*c+1);
p[c]=upval(2*c)&upval(2*c+1);
}
};
ST S;
set<ll> borders; ll N, H;
void check(ll x)
{
if(x==0 || x>=H) {return;}
borders.erase(x);
ll val_left = S.query(x-1,x-1).a; ll val = S.query(x,x).a;
if(val_left!=val) {borders.insert(x);}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cout.precision(20);
cin>>N; vector<pl> p; pl cur; H=0LL;
REP(i,0,N) {cin>>cur.ff>>cur.ss; H=max(H,cur.ff); cur.ff--; p.pb(cur);}
vector<ll> xx(H,0); S = ST(xx); sort(whole(p)); borders.insert(0);
ll thisH, K, L; set<ll>::iterator it; ll start, finish;
REP(i,0,N)
{
thisH = p[i].ff; K = p[i].ss;
L = thisH-K+1;
it = borders.upper_bound(L); it--; start = *it;
it++; if(it==borders.end()) {finish = thisH;} else {finish = min(*it -1,thisH);}
S.update(1,finish+1,thisH); K-=(thisH-finish);
S.update(1,start,start+K-1);
check(start); check(start+K); check(finish+1); check(thisH+1);
}
ll ans = 0LL;
REP(i,0,H)
{
thisH = S.query(i,i).a;
ans+=(thisH*(thisH-1LL))/2LL; ans%=mod;
}
cout<<ans<<endl;
return 0;
}
Compilation message
sails.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization ("O3")
|
sails.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
3532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
4436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
7000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
13452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
13644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
249 ms |
13648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
