| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1092572 |
2024-09-24T12:30:18 Z |
MrPavlito |
Sails (IOI07_sails) |
C++17 |
|
937 ms |
10592 KB |
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
vector<int> seg(MAXN<<2,-1);
vector<int> lazy(MAXN<<2, 0);
int rez;
void push(int nod, int tl, int tr)
{
if(lazy[nod] == 0) return;
if(tl != tr)
{
lazy[nod<<1] += lazy[nod];
lazy[nod<<1|1] += lazy[nod];
}
seg[nod] += lazy[nod];
lazy[nod] = 0;
}
int query(int nod, int tl, int tr, int l, int r)
{
push(nod, tl, tr);
if(tl > r || tr < l || tl > tr) return -inf;
if(tl >= l && tr <= r) return seg[nod];
int mid = tl + tr >> 1;
return max(query(nod<<1, tl, mid, l, r), query(nod<<1|1, mid + 1, tr, l, r));
}
void update(int nod, int tl, int tr, int l, int r)
{
push(nod, tl, tr);
if(tl > r || tr < l || tl > tr || l > r) return;
if(tl >= l && tr <= r)
{
lazy[nod]++;
push(nod, tl, tr);
return;
}
int mid = tl + tr >> 1;
update(nod<<1, tl, mid, l, r);
update(nod<<1|1, mid + 1, tr, l, r);
seg[nod] = max(seg[nod<<1], seg[nod<<1|1]);
}
void get(int nod, int tl, int tr, int index)
{
push(nod, tl, tr);
rez = min(rez, seg[nod]);
if(tl == tr) return;
int mid = tl + tr >> 1;
if(index <= mid) get(nod<<1, tl, mid, index);
else get(nod<<1|1, mid + 1, tr, index);
}
signed main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tt = 1;
while(tt--)
{
int n;
cin >> n;
vector<pii> niz(n);
int mx = 0;
for(int i = 0; i < n; i++)
{
cin >> niz[i].fi >> niz[i].sc;
mx = max(mx, niz[i].fi);
}
sort(all(niz));
for(auto x: niz)cout << x.fi << " " << x.sc << endl;
for(int i = 0; i < n; i++)
{
int p = query(1, 1, mx, 1, niz[i].fi);
int tr = niz[i].sc;
int lb = niz[i].fi;
int l = 1, r = niz[i].fi, ub = 1;
while(l <= r)
{
int mid = l + r >> 1;
if(query(1, 1, mx, mid, niz[i].fi) == p)
{
ub = mid;
l = mid + 1;
}
else r = mid - 1;
}
l = 1; r = niz[i].fi;
while(l <= r)
{
int mid = l + r >> 1;
rez = -1;
if(query(1, 1, mx, 1, mid) == p)
{
lb = mid;
r = mid - 1;
}
else l = mid + 1;
}
int pomoc = tr - lb + 1;
update(1, 1, mx, 1, lb - 1);
update(1, 1, mx, niz[i].fi - pomoc + 1, niz[i].fi);
/*
for(int j = 1; j <= mx; j++)
{
rez = inf;
get(1, 1, mx, j);
cout << rez << " ";
}
cout << endl;
*/
}
int finalrez = 0;
for(int j = 1; j <= mx; j++)
{
rez = inf;
get(1, 1, mx, j);
finalrez += (rez) * (rez + 1) / 2;
}
cout << finalrez << endl;
}
}
Compilation message
sails.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = tl + tr >> 1;
| ~~~^~~~
sails.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:50:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = tl + tr >> 1;
| ~~~^~~~
sails.cpp: In function 'void get(long long int, long long int, long long int, long long int)':
sails.cpp:61:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = tl + tr >> 1;
| ~~~^~~~
sails.cpp: In function 'int main()':
sails.cpp:92:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = l + r >> 1;
| ~~^~~
sails.cpp:103:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int mid = l + r >> 1;
| ~~^~~
sails.cpp:89:39: warning: variable 'ub' set but not used [-Wunused-but-set-variable]
89 | int l = 1, r = niz[i].fi, ub = 1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
6980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
7664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
432 ms |
8616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
738 ms |
9628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
875 ms |
10068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
937 ms |
10592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
