oj.uz

Submission #1010517

# Submission time Handle Problem Language Result Execution time Memory
1010517 2024-06-29T07:31:43 Z modwwe Examination (JOI19_examination) C++17
100 / 100
 159 ms 14108 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
///     fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
ib a[100002];
vector<ib> v3[100002];
vector<ic> v2[100002];
vector<int> v;
vector<int> v4;
vector<int> v5;
int ans[100002];
struct BIT
{
    int bit[100001];
    void upd(int x)
    {
        for(x; x; x-=x&-x) bit[x]++;
    }
    int get(int x)
    {
        int s=0;
        for(x; x<=n; x+=x&-x)s+=bit[x];
        return s;
    }

} bit1,bit2;
bool cmp(ib a,ib b)
{
    return a.a<b.a;
}

void phongbeo()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i].a>>a[i].b,v.pb(a[i].a),v4.pb(a[i].b),v5.pb(a[i].b+a[i].a);
    sort(v4.begin(),v4.end());
    sort(v5.begin(),v5.end());
    sort(v.begin(),v.end());
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r>>s2;
        s3=s2-r;
        s4=lower_bound(v.begin(),v.end(),l)-v.begin()+1;
        if(s3>l)
        s3=lower_bound(v.begin(),v.end(),s3)-v.begin()+1;
else s3=0;
        v3[max(s4,s3)].pb({r,i});
        if(s3>s4)
        {
            v2[s4].pb({s2,1,i});
            v2[s3].pb({s2,-1,i});
        }
    }
    for(int i=n; i>=1; --i)
    {
        s2=a[i].b;
        s3=a[i].a+a[i].b;
        s2=lower_bound(v4.begin(),v4.end(),s2)-v4.begin()+1;
        s3=lower_bound(v5.begin(),v5.end(),s3)-v5.begin()+1;
        bit1.upd(s2);
        bit2.upd(s3);
        for(auto x:v2[i])
        {
            s2=x.a;
            s2=lower_bound(v5.begin(),v5.end(),s2)-v5.begin()+1;
            ans[x.c]+=bit2.get(s2)*x.b;
        }
        for(auto x:v3[i])
        {
            s2=x.a;
            s2=lower_bound(v4.begin(),v4.end(),s2)-v4.begin()+1;
            ans[x.b]+=bit1.get(s2);
        }
    }
    for(int i=1; i<=m; i++)
        cout<<ans[i],down

    }

Compilation message

examination.cpp:19:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int inf=1e18;
      |               ^~~~
examination.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      | ^~~~
examination.cpp: In member function 'void BIT::upd(int)':
examination.cpp:69:13: warning: statement has no effect [-Wunused-value]
   69 |         for(x; x; x-=x&-x) bit[x]++;
      |             ^
examination.cpp: In member function 'int BIT::get(int)':
examination.cpp:74:13: warning: statement has no effect [-Wunused-value]
   74 |         for(x; x<=n; x+=x&-x)s+=bit[x];
      |             ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 5 ms 5304 KB Output is correct
8 Correct 5 ms 5212 KB Output is correct
9 Correct 6 ms 5264 KB Output is correct
10 Correct 5 ms 5352 KB Output is correct
11 Correct 4 ms 5208 KB Output is correct
12 Correct 4 ms 5212 KB Output is correct
13 Correct 5 ms 5212 KB Output is correct
14 Correct 6 ms 5212 KB Output is correct
15 Correct 5 ms 5140 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 5 ms 5208 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10436 KB Output is correct
2 Correct 109 ms 10488 KB Output is correct
3 Correct 111 ms 10588 KB Output is correct
4 Correct 85 ms 10184 KB Output is correct
5 Correct 86 ms 10180 KB Output is correct
6 Correct 45 ms 9672 KB Output is correct
7 Correct 99 ms 9924 KB Output is correct
8 Correct 105 ms 10432 KB Output is correct
9 Correct 96 ms 10180 KB Output is correct
10 Correct 72 ms 9836 KB Output is correct
11 Correct 72 ms 9920 KB Output is correct
12 Correct 32 ms 8756 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10436 KB Output is correct
2 Correct 109 ms 10488 KB Output is correct
3 Correct 111 ms 10588 KB Output is correct
4 Correct 85 ms 10184 KB Output is correct
5 Correct 86 ms 10180 KB Output is correct
6 Correct 45 ms 9672 KB Output is correct
7 Correct 99 ms 9924 KB Output is correct
8 Correct 105 ms 10432 KB Output is correct
9 Correct 96 ms 10180 KB Output is correct
10 Correct 72 ms 9836 KB Output is correct
11 Correct 72 ms 9920 KB Output is correct
12 Correct 32 ms 8756 KB Output is correct
13 Correct 133 ms 12132 KB Output is correct
14 Correct 122 ms 11204 KB Output is correct
15 Correct 114 ms 10584 KB Output is correct
16 Correct 102 ms 12264 KB Output is correct
17 Correct 84 ms 11484 KB Output is correct
18 Correct 45 ms 10080 KB Output is correct
19 Correct 124 ms 12120 KB Output is correct
20 Correct 126 ms 11980 KB Output is correct
21 Correct 133 ms 12928 KB Output is correct
22 Correct 73 ms 9508 KB Output is correct
23 Correct 78 ms 9928 KB Output is correct
24 Correct 32 ms 8656 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 5 ms 5304 KB Output is correct
8 Correct 5 ms 5212 KB Output is correct
9 Correct 6 ms 5264 KB Output is correct
10 Correct 5 ms 5352 KB Output is correct
11 Correct 4 ms 5208 KB Output is correct
12 Correct 4 ms 5212 KB Output is correct
13 Correct 5 ms 5212 KB Output is correct
14 Correct 6 ms 5212 KB Output is correct
15 Correct 5 ms 5140 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 5 ms 5208 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 110 ms 10436 KB Output is correct
20 Correct 109 ms 10488 KB Output is correct
21 Correct 111 ms 10588 KB Output is correct
22 Correct 85 ms 10184 KB Output is correct
23 Correct 86 ms 10180 KB Output is correct
24 Correct 45 ms 9672 KB Output is correct
25 Correct 99 ms 9924 KB Output is correct
26 Correct 105 ms 10432 KB Output is correct
27 Correct 96 ms 10180 KB Output is correct
28 Correct 72 ms 9836 KB Output is correct
29 Correct 72 ms 9920 KB Output is correct
30 Correct 32 ms 8756 KB Output is correct
31 Correct 133 ms 12132 KB Output is correct
32 Correct 122 ms 11204 KB Output is correct
33 Correct 114 ms 10584 KB Output is correct
34 Correct 102 ms 12264 KB Output is correct
35 Correct 84 ms 11484 KB Output is correct
36 Correct 45 ms 10080 KB Output is correct
37 Correct 124 ms 12120 KB Output is correct
38 Correct 126 ms 11980 KB Output is correct
39 Correct 133 ms 12928 KB Output is correct
40 Correct 73 ms 9508 KB Output is correct
41 Correct 78 ms 9928 KB Output is correct
42 Correct 32 ms 8656 KB Output is correct
43 Correct 159 ms 12432 KB Output is correct
44 Correct 120 ms 12228 KB Output is correct
45 Correct 120 ms 11460 KB Output is correct
46 Correct 103 ms 12380 KB Output is correct
47 Correct 92 ms 11584 KB Output is correct
48 Correct 47 ms 10812 KB Output is correct
49 Correct 130 ms 12232 KB Output is correct
50 Correct 113 ms 12864 KB Output is correct
51 Correct 146 ms 14108 KB Output is correct
52 Correct 81 ms 10684 KB Output is correct
53 Correct 75 ms 9924 KB Output is correct