/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 500007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
/// code from USACO examples
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;
/// ------ Segment Treee --------
int Nseg[2];
struct SEGNODE {
multiset<int> s;
};
SEGNODE seg[6*MAXV]; /// max 2e5 unique y, which needs 2^19 for Nseg
void buildSeg(int v = 1, int l = Nseg[0], int r = Nseg[1]) {
if(l == r) { // leaf
seg[v].s.clear();
return;
}
int mid = (l + r) / 2;
buildSeg(2*v, l, mid); buildSeg(2*v+1, mid+1, r);
seg[v].s.clear();
}
ll querySeg(int qle, int qri, int lim, int v = 1, int l = Nseg[0], int r = Nseg[1]) {
if(r < qle || l > qri) return 0LL;
if(qle <= l && r <= qri) {
multiset<int>::iterator itup = seg[v].s.upper_bound(lim);
return distance(itup, seg[v].s.end());
}
int mid = (l + r) / 2;
return querySeg(qle, qri, lim, 2*v, l, mid) + querySeg(qle, qri, lim, 2*v+1, mid+1, r);
}
void updateSeg(int vtx, int val, int v = 1, int l = Nseg[0], int r = Nseg[1]){
if(l == r) { // leaf
seg[v].s.insert(val);
return;
}
int mid = (l + r) / 2;
(vtx <= mid) ? updateSeg(vtx, val, 2*v, l, mid) : updateSeg(vtx, val, 2*v+1, mid+1, r);
seg[v].s.insert(val);
}
void replaceSeg(int vtx, int val0, int val1, int v = 1, int l = Nseg[0], int r = Nseg[1]){
if(l == r) { // leaf
seg[v].s.erase(val0);
seg[v].s.insert(val1);
return;
}
int mid = (l + r) / 2;
(vtx <= mid) ? replaceSeg(vtx, val0, val1, 2*v, l, mid) : replaceSeg(vtx, val0, val1, 2*v+1, mid+1, r);
seg[v].s.erase(val0);
seg[v].s.insert(val1);
}
vector<int> countScans( vector<int> A, vector<int> X, vector<int> V) {
debug = true; submit = false;
if(submit) setIO("testName");
int i, j, k;
vector<ll> ans;
ll total = 0;
Nseg[0] = 0; Nseg[1] = A.size() - 1;
buildSeg();
for(i=0; i<A.size();i++) {
updateSeg(i, A[i]);
}
for(i=0; i<A.size();i++) {
ll q = (i>=1) ? querySeg(0, i-1, A[i]) : 0LL;
ans.pb(q);
total += q;
}
for(i=0;i<X.size();i++) {
replaceSeg(X[i], A[X[i]], V[i]);
total -= ans[X[i]];
ans[X[i]] = (X[i]>=1) ? querySeg(0, X[i]-1, V[i]) : 0;
total += ans[X[i]];
A[X[i]] = V[i];
cout << total << endl;
}
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(i=0; i<A.size();i++) {
| ~^~~~~~~~~
bubblesort2.cpp:122:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(i=0; i<A.size();i++) {
| ~^~~~~~~~~
bubblesort2.cpp:128:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(i=0;i<X.size();i++) {
| ~^~~~~~~~~
bubblesort2.cpp:112:12: warning: unused variable 'j' [-Wunused-variable]
112 | int i, j, k;
| ^
bubblesort2.cpp:112:15: warning: unused variable 'k' [-Wunused-variable]
112 | int i, j, k;
| ^
bubblesort2.cpp:137:1: warning: no return statement in function returning non-void [-Wreturn-type]
137 | }
| ^
bubblesort2.cpp: In function 'void setIO(std::string)':
bubblesort2.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
53 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
54 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
265 ms |
286700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
265 ms |
286700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6790 ms |
328236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
265 ms |
286700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
