| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1367488 | temurbek1371 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vb vector<bool>
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define endl '\n'
#define maxx(x) *max_element(all(x))
#define pii pair<int,int>
#define minn(x) *min_element(all(x))
#define vpii vector<pii>
#define di deque<int>
#define mii map<int,int>
#define vap(x) vector<array<int,x>>
constexpr int MOD = (1e9 + 7);
constexpr int inf = 1e18;
void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ostream& operator<<(ostream& out, vi& a) {
for (int i = 0; a.size() > i; i++)out << a[i] << ' ';
return out;
}
ostream& operator<<(ostream& out, vector<vi>& a) {
for (auto& row : a) {
for (auto& elem : row) out << elem << ' ';
out << '\n';
}
return out;
}
istream& operator>>(istream& in, vi& a) {
for (int i = 0; a.size() > i; i++) in >> a[i];
return in;
}
istream& operator>>(istream& in, vector<vi>& a) {
for(int i = 0;i<a.size();i++){
for(int j = 0;j<a[i].size();j++){
in >> a[i][j];
}
}
return in;
}
int sumofvecor(vi a){
int sm = 0;
for(int i = 0;i<a.size();i++)sm+=a[i];
return sm;
}
bool isprime(int number){
for(int i = 2;i*i<=number;i++){
if(number%i==0)return false;
}
return number>=2;
}
void file_io() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
void solve();
signed main(signed argc, char *argv[]) {
clock_t start = clock();
fast_io();
// file_io();
if (argc > 1 && string(argv[1]) == "gg") file_io();
int test = 1;
// cin >> test;
while (test--) {
solve();
}
cerr << "Vaqt " << double(clock() - start) / double(CLOCKS_PER_SEC) * 1000 << " ms\n";
}
void solve(){
int n,q;
cin>>n>>q;
vpii a(n);
for(int i = 0;i<n;i++){
cin>>a[i].first;
a[i].second=i;
}
vector<array<int,5>> quer;
for(int i = 0;i<q;i++){
int l,r,c,d;
cin>>l>>r>>c>>d;
l--,r--;
quer.push_back({d,l,r,i,1});
quer.push_back({c-1,l,r,i,-1});
}
sort(all(quer));
sort(all(a));
vi ans(q);
vi bit(n);
int ind = 0;
auto add = [&](int i){
for(;i<n;i = (i|(i+1)))bit[i]++;
};
auto get = [&](int i){
int sm = 0;
for(;i>=0;i = (i&(i+1))-1)sm+=bit[i];
return sm;
};
for(auto q:quer){
int cr = q[0];
while(ind<n && a[ind].first<=cr)add(a[ind++].second);
int l = q[1],r = q[2],id = q[3],s = q[4];
int ca = get(r)-get(l-1);
ans[id]+=s*ca;
}
for(int i:ans)cout<<i<<endl;
}