oj.uz

Submission #158898

# Submission time Handle Problem Language Result Execution time Memory
158898 2019-10-19T11:44:59 Z georgerapeanu Examination (JOI19_examination) C++11
0 / 100
 1167 ms 66404 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct query_t{
    int a,b,c;
    int id;

    bool operator < (const query_t &other)const{
        if(c != other.c)return c > other.c;
        return id < other.id;
    }
};

class AIB2d{
public:
    int n;
    vector<vector<int> > stuff;
    vector<vector<int> > aib;

    AIB2d(int n){
        this->n = n;
        stuff = vector<vector<int>>(n + 1,vector<int>(1,-1));
        aib = vector<vector<int>>(n + 1,vector<int>(1,-1));
    }

    void preupdate(int x,int y){
        for(int xx = x;xx > 0;xx -= (-xx & xx)){
            for(int yy = y;yy > 0;yy -= (-yy & y)){
                stuff[xx].push_back(yy);
            }
        }
    }

    void init(){
        for(int i = 1;i <= n;i++){
            sort(stuff[i].begin(),stuff[i].end());
            stuff[i].resize(unique(stuff[i].begin(),stuff[i].end()) - stuff[i].begin());
            aib[i] = vector<int>(stuff[i].size(),0);
        }
    }

    void update(int x,int y,int val){
        for(int xx = x;xx > 0;xx -= (-xx & xx)){
            for(int yy = lower_bound(stuff[xx].begin(),stuff[xx].end(),y) - stuff[xx].begin();yy > 0;yy -= (-yy & yy)){
                aib[xx][yy] += val;
            }
        }
    }

    int query(int x,int y){
        int ans = 0;

        for(int xx = x;xx <= n;xx += (-xx & xx)){
            for(int yy = lower_bound(stuff[xx].begin(),stuff[xx].end(),y) - stuff[xx].begin();yy < (int)stuff[xx].size();yy += (-yy & yy)){
                ans += aib[xx][yy];
            }
        }

        return ans;
    }
};

int n,q;
int ans[100005];
vector<query_t> events;

int main(){
    scanf("%d %d",&n,&q);

    map<int,int> to_norm;

    for(int i = 1;i <= n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        events.push_back({x,y,x + y,i - n});
        to_norm[x] = 1;
    }

    for(int i = 1;i <= q;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        events.push_back({a,b,c,i});
        to_norm[a] = 1;
    }

    sort(events.begin(),events.end());

    int last = 0;
    for(auto &it:to_norm){
        it.second = ++last;
    }
    AIB2d aib(last);

    for(auto it:events){
        if(it.id <= 0){
            aib.preupdate(to_norm[it.a],it.b);
        }
    }
    
    aib.init();

    for(auto it:events){
        if(it.id <= 0){
            aib.update(to_norm[it.a],it.b,1);
        }
        else{
            ans[it.id] = aib.query(to_norm[it.a],it.b);    
        }
    }

    for(int i = 1;i <= q;i++){
        printf("%d\n",ans[i]);
    }

    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
examination.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~
examination.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 30 ms 3832 KB Output is correct
8 Correct 29 ms 3804 KB Output is correct
9 Correct 29 ms 3832 KB Output is correct
10 Incorrect 12 ms 1660 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 30 ms 3832 KB Output is correct
8 Correct 29 ms 3804 KB Output is correct
9 Correct 29 ms 3832 KB Output is correct
10 Incorrect 12 ms 1660 KB Output isn't correct
11 Halted 0 ms 0 KB -