| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 568742 |
2022-05-26T06:52:04 Z |
tqbfjotld |
Fish 2 (JOI22_fish2) |
C++14 |
|
183 ms |
102648 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000005;
struct dat{
vector<int> lblockvals;
vector<int> lblockpos;
vector<int> lblocknum;
vector<int> lblockpsum;
vector<int> rblockvals;
vector<int> rblockpos;
vector<int> rblocknum;
vector<int> rblockpsum;
int numfin;
int totsz;
int len;
dat(){
numfin = 0;
totsz = 0;
len = 0;
}
dat(int num){
numfin = 1;
totsz = num;
len = 1;
lblockpos.push_back(0);
lblocknum.push_back(0);
lblockvals.push_back(num);
lblockpsum.push_back(num);
rblockpos.push_back(0);
rblocknum.push_back(0);
rblockvals.push_back(num);
rblockpsum.push_back(num);
}
};
dat mer(dat a, dat b){
//printf("mer %d and %d\n",a.numfin,b.numfin);
dat ans = dat();
ans.totsz = a.totsz+b.totsz;
ans.len = a.len+b.len;
for (int x = 0; x<a.lblocknum.size(); x++){
ans.lblocknum.push_back(a.lblocknum[x]);
ans.lblockpos.push_back(a.lblockpos[x]);
ans.lblockvals.push_back(a.lblockvals[x]);
ans.lblockpsum.push_back(a.lblockpsum[x]);
//printf("lblock %d %d %d %d\n",a.lblocknum[x],a.lblockpos[x],a.lblockvals[x],a.lblockpsum[x]);
}
for (int x = 0; x<b.rblocknum.size(); x++){
ans.rblocknum.push_back(b.rblocknum[x]);
ans.rblockpos.push_back(b.rblockpos[x]);
ans.rblockvals.push_back(b.rblockvals[x]);
ans.rblockpsum.push_back(b.rblockpsum[x]);
//printf("rblock %d %d %d %d\n",b.rblocknum[x],b.rblockpos[x],b.rblockvals[x],b.rblockpsum[x]);
}
//printf("hi\n");
int t1 = a.totsz;
int li,ri;
bool canfin = true;
for (int x = 0; x<b.lblocknum.size(); x++){
if (b.lblockvals[x]<=t1){
t1 += b.lblockpsum[x];
if (t1>INF) t1 = INF;
}
else{
li = ans.lblocknum.size();
canfin = false;
//assert(!ans.lblockpsum.empty());
ans.lblockpsum.back() += t1-a.totsz;
ans.lblockpos.push_back(b.lblockpos[x]+a.len);
ans.lblocknum.push_back(a.numfin);
ans.lblockvals.push_back(b.lblockvals[x]);
ans.lblockpsum.push_back(b.totsz-(t1-a.totsz));
break;
}
}
if (canfin){
ans.lblockpsum.back() += b.totsz;
ans.numfin += a.numfin;
}
t1 = b.totsz;
canfin = true;
for (int x = 0; x<a.rblocknum.size(); x++){
if (a.rblockvals[x]<=t1){
t1 += a.rblockpsum[x];
if (t1>INF) t1 = INF;
}
else{
ri = ans.rblocknum.size();
canfin = false;
//assert(!ans.rblockpsum.empty());
ans.rblockpsum.back() += t1-b.totsz;
ans.rblockpos.push_back(a.rblockpos[x]+b.len);
ans.rblocknum.push_back(b.numfin);
ans.rblockvals.push_back(a.rblockvals[x]);
ans.rblockpsum.push_back(a.totsz-(t1-b.totsz));
break;
}
}
if (canfin){
ans.rblockpsum.back() += a.totsz;
ans.numfin += b.numfin;
}
//printf("hi\n");
t1 = 0;
int t2 = 0;
int maxv = 0;
int sum1 = 0;
for (int x = 0; x<a.rblocknum.size(); x++){
sum1+= a.rblockpsum[x];
}
for (int x = 1; x<a.rblocknum.size(); x++){
//printf("arblock %d %d %d %d\n",a.rblocknum[x],a.rblockpos[x],a.rblockvals[x],a.rblockpsum[x]);
t1 += a.rblocknum[x];
t2 += a.rblockpsum[x-1];
sum1 -= a.rblockpsum[x-1];
t2 = min(t2,INF);
bool added = false;
while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
t2 += b.lblockpsum[maxv];
t2 = min(t2,INF);
maxv++;
added = true;
}
if (a.rblockvals[x]>t2){
if (maxv==b.lblocknum.size()){
if (ans.rblockpos.back()==b.len+a.rblockpos[x]){
ans.rblocknum.back()+=t1;
}
else{
ans.rblockpsum.back() -= sum1;
ans.rblockpos.push_back(b.len+a.rblockpos[x]);
ans.rblocknum.push_back(t1);
ans.rblockvals.push_back(a.rblockvals[x]);
ans.rblockpsum.push_back(sum1);
}
}
t1 = 0;
}
}
t2 += a.rblockpsum.back();
while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
t2 += b.lblockpsum[maxv];
t2 = min(t2,INF);
maxv++;
}
//printf("maxv = %d\n",maxv);
if (maxv==b.lblocknum.size()){
ans.numfin += t1;
}
else{
ans.lblocknum[li] += t1;
}
t1 = 0;
t2 = 0;
maxv = 0;
int sum2 = 0;
for (int x = 0; x<b.lblocknum.size(); x++){
sum2 += b.lblockpsum[x];
}
for (int x = 1; x<b.lblocknum.size(); x++){
//printf("blblock %d %d %d %d\n",b.lblocknum[x],b.lblockpos[x],b.lblockvals[x],b.lblockpsum[x]);
t1 += b.lblocknum[x];
t2 += b.lblockpsum[x-1];
sum2 -= b.lblockpsum[x-1];
t2 = min(t2,INF);
bool added = false;
while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
t2 += a.rblockpsum[maxv];
t2 = min(t2,INF);
maxv++;
added = true;
}
if (b.lblockvals[x]>t2){
if (maxv==a.rblocknum.size()){
if (ans.lblockpos.back()==a.len+b.lblockpos[x]){
ans.lblocknum.back()+=t1;
}
else{
ans.lblockpsum.back() -= sum2;
ans.lblockpos.push_back(a.len+b.lblockpos[x]);
ans.lblocknum.push_back(t1);
ans.lblockvals.push_back(b.lblockvals[x]);
ans.lblockpsum.push_back(sum2);
}
}
t1 = 0;
}
}
t2 += b.lblockpsum.back();
while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
t2 += a.rblockpsum[maxv];
t2 = min(t2,INF);
maxv++;
}
if (maxv==a.rblocknum.size()){
ans.numfin += t1;
}
else{
ans.rblocknum[ri] += t1;
}
assert(ans.lblocknum.size()==ans.lblockpos.size());
assert(ans.lblockpos.size()==ans.lblockvals.size());
assert(ans.lblockpsum.size()==ans.lblockvals.size());
return ans;
}
int arr[100005];
struct node{
int s,e;
dat v;
node *l,*r;
node (int _s, int _e){
s = _s;
e = _e;
if (s==e){
v = dat(arr[s]);
}
else{
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
v = mer(l->v,r->v);
//printf("node %d to %d has numfin %d\n",s,e,v.numfin);
}
}
dat qu(int a, int b){
//printf("node %d to %d, %d %d\n",s,e,a,b);
if (a<=s && e<=b){
return v;
}
if (b<=(s+e)/2){
return l->qu(a,b);
}
if (a>(s+e)/2){
return r->qu(a,b);
}
//printf("end %d %d\n",s,e);
return mer(l->qu(a,b),r->qu(a,b));
}
void upd(int pos){
if (s==e){
v = dat(arr[s]);
return;
}
if (pos<=(s+e)/2){
l->upd(pos);
}
else{
r->upd(pos);
}
v = mer(l->v,r->v);
}
}*root;
int main(){
int n;
scanf("%d",&n);
for (int x = 1; x<=n; x++){
scanf("%d",&arr[x]);
}
root = new node(1,n);
int q;
scanf("%d",&q);
while (q--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if (a==1){
arr[b] = c;
root->upd(b);
}
else{
printf("%d\n",root->qu(b,c).numfin);
}
}
}
Compilation message
fish2.cpp: In function 'dat mer(dat, dat)':
fish2.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int x = 0; x<a.lblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int x = 0; x<b.rblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int x = 0; x<b.lblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int x = 0; x<a.rblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int x = 0; x<a.rblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int x = 1; x<a.rblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
| ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if (maxv==b.lblocknum.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:119:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
119 | bool added = false;
| ^~~~~
fish2.cpp:143:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | while (maxv<b.lblocknum.size() && b.lblockvals[maxv]<=t2){
| ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:149:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if (maxv==b.lblocknum.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for (int x = 0; x<b.lblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (int x = 1; x<b.lblocknum.size(); x++){
| ~^~~~~~~~~~~~~~~~~~~
fish2.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
| ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:176:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | if (maxv==a.rblocknum.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp:168:14: warning: variable 'added' set but not used [-Wunused-but-set-variable]
168 | bool added = false;
| ^~~~~
fish2.cpp:192:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | while (maxv<a.rblocknum.size() && a.rblockvals[maxv]<=t2){
| ~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp:197:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | if (maxv==a.rblocknum.size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~
fish2.cpp: In function 'int main()':
fish2.cpp:259:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
259 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
fish2.cpp:261:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
261 | scanf("%d",&arr[x]);
| ~~~~~^~~~~~~~~~~~~~
fish2.cpp:265:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
265 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
fish2.cpp:268:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
268 | scanf("%d%d%d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
fish2.cpp: In function 'dat mer(dat, dat)':
fish2.cpp:201:25: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
201 | ans.rblocknum[ri] += t1;
| ^
fish2.cpp:153:25: warning: 'li' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | ans.lblocknum[li] += t1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
0 ms |
308 KB |
Output is correct |
| 5 |
Runtime error |
5 ms |
1476 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
183 ms |
102648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
0 ms |
308 KB |
Output is correct |
| 5 |
Runtime error |
5 ms |
1476 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
183 ms |
102648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
183 ms |
102648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
0 ms |
308 KB |
Output is correct |
| 5 |
Runtime error |
5 ms |
1476 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
