oj.uz

Submission #535040

# Submission time Handle Problem Language Result Execution time Memory
535040 2022-03-09T10:42:38 Z Carmel_Ab1 Examination (JOI19_examination) C++17
20 / 100
 201 ms 19604 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}

struct Seg{

    int l,r,m,sum=0;
    Seg* lp=0,*rp=0;

    Seg(int l,int r):l(l),r(r),m((l+r)/2){}
    void expand(){
        if(!lp)lp=new Seg(l,m);
        if(!rp)rp=new Seg(m,r);
    }

    void upd(int i,int v){
        sum+=v;
        if(l+1==r)return;
        expand();

        if(i<m)
            lp->upd(i,v);
        else
            rp->upd(i,v);
        sum=lp->sum+rp->sum;
    }

    int qur(int a,int b){
        if(r<=a || b<=l)return 0;
        else if(a<=l && r<=b)return sum;
        expand();
        return lp->qur(a,b)+rp->qur(a,b);
    }

};
void solve() {
    int n,q;
    cin >> n >> q;

    vpi a(n);
    read(a);
    sort(all(a),greater<pi>());

    vvi queries(q,vi(4));
    for(int i=0; i<q; i++){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
        queries[i][3]=i;
    }
    sort(all(queries),greater<vi>());
    vi ans(q);

    Seg ST(0,1e9+1);

    int prv=0;

    for(int i=0,j=0; i<q; i++){
        int x=queries[i][0],y=queries[i][1],z=queries[i][2];
        while(j<n && a[j].first>=x){
            ST.upd(a[j].second,1);
            j++;
        }
        if(!j)continue;

        int ix=queries[i][3];
        ans[ix]=ST.qur(y,1e9 +1);
    }

    for(int x:ans)cout << x << "\n";
}

Compilation message

examination.cpp: In function 'void solve()':
examination.cpp:128:45: warning: unused variable 'z' [-Wunused-variable]
  128 |         int x=queries[i][0],y=queries[i][1],z=queries[i][2];
      |                                             ^
examination.cpp:125:9: warning: unused variable 'prv' [-Wunused-variable]
  125 |     int prv=0;
      |         ^~~
examination.cpp: In function 'void usaco(std::string)':
examination.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 19104 KB Output is correct
2 Correct 187 ms 19100 KB Output is correct
3 Correct 160 ms 19128 KB Output is correct
4 Correct 97 ms 9224 KB Output is correct
5 Correct 136 ms 18356 KB Output is correct
6 Correct 87 ms 8476 KB Output is correct
7 Correct 201 ms 19100 KB Output is correct
8 Correct 158 ms 18740 KB Output is correct
9 Correct 144 ms 18552 KB Output is correct
10 Correct 107 ms 18072 KB Output is correct
11 Correct 87 ms 8984 KB Output is correct
12 Correct 72 ms 8132 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 19104 KB Output is correct
2 Correct 187 ms 19100 KB Output is correct
3 Correct 160 ms 19128 KB Output is correct
4 Correct 97 ms 9224 KB Output is correct
5 Correct 136 ms 18356 KB Output is correct
6 Correct 87 ms 8476 KB Output is correct
7 Correct 201 ms 19100 KB Output is correct
8 Correct 158 ms 18740 KB Output is correct
9 Correct 144 ms 18552 KB Output is correct
10 Correct 107 ms 18072 KB Output is correct
11 Correct 87 ms 8984 KB Output is correct
12 Correct 72 ms 8132 KB Output is correct
13 Incorrect 191 ms 19604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -