# TOI練習賽202503潛力組
### [第一題](https://zerojudge.tw/ShowProblem?problemid=q374)
#### 考點：貪心、位元運算
#### 實作方法
##### 子題一
觀察到`T=1`且`a,b`<$2^8$，直接暴力枚舉所有情況`(0~a，包含a)`，再求最大最小值
::: spoiler Python 20% code

t=int(input())
a,b=map(int, input().split())
ans1,ans2=-1,float('inf')
for i in range(a+1):
    for j in range(i+1):
        if (i|j)==a and (i&j)==b:
            ans1=max(ans1,i-j)
            ans2=min(ans2,i-j)
print(ans1,ans2)

:::
:::spoiler C++ 20% code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b,t;
    cin>>t>>a >> b;

    int ans1 = -1;
    int ans2 = INT_MAX;  // Use INT_MAX to represent infinity

    for (int i = 0; i <= a; ++i) {
        for (int j = 0; j <= i; ++j) {
            if ((i | j) == a && (i & j) == b) {
                ans1 = max(ans1, i - j);
                ans2 = min(ans2, i - j);
            }
        }
    }

    cout << ans1 << " " << ans2 << endl;
    return 0;
}

:::
##### AC
一、貪心
觀察到題目所求為絕對值最大和最小，並給出and和or的結果。如果`and`該位元為`1`，則兩個數的位元皆為`1`，故對於答案不會有影響。
但如果`or`的位元為`1`，and位元為`0`，則
1.求最大差距：把所有符合條件的結果給其中一個數，即為答案。更仔細觀察，其實就是`a-b`。
2.求最小差距：把第一個符合條件的給其中一個，剩下的給另外一個，就相減即為答案。
例如`11 1`
`11`=>轉換成二進制 `1011`
`1`=>二進制(補前導0) `0001`
and為0且or為1 `1010`
取最大 `1010=10`
取最小 `1000-0010=8-2=6`
由於最多到$2^{30}$-1，故每次最多檢查30位，時間複雜度O($1$)。
整體時間複雜度O($T$)。
###### 註：由於不可能存在and位元為1且or位元為0，故可將條件改為互斥(XOR)成立。
:::spoiler Python AC(0.2s, 3.3MB) code

for _ in range(int(input())):
    a,b=map(int, input().split())
    ans,flag=0,0
    a_xor_b=a^b
    for i in range(30,-1,-1):
        if (a_xor_b>>i)&1:
            if flag==0:
                ans+=(1<<(i))
                flag=1
            else:ans-=(1<<(i))
    print(a-b,ans)
    

:::
:::spoiler C++ AC(48ms, 324KB) code 1

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a,b;
    cin>>a>>b;
    cout<<a-b<<" ";
    int ans=0;
    bool flag=true;
    int a_xor_b=a^b;
    for(int i=30;i>=0;i--){
        if (((a_xor_b>>i)&1)){
            if (flag){ans+=(1<<i);flag=false;}
            else ans-=(1<<i);
        }
    }
    cout<<ans<<endl;
    
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
}

:::
:::spoiler C++ AC(48ms, 332KB) code 2(使用內建函式)

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int a,b;
    cin>>a>>b;
    bool flag=false;
    int a_xor_b=a^b,ans;
    int c=__builtin_clz(a_xor_b);//計算第一高位的1前面有幾個0，傳入unsigned int
    ans=(1<<(32-c-1));
    ans-=a_xor_b^ans;
    cout<<a-b<<" "<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
}

:::
### [第二題](https://zerojudge.tw/ShowProblem?problemid=q375)
#### 考點：滑動窗口
#### 實作方法
##### 子題一&子題二
發現子題一`n<=50`，子題二`n<=1000`直接枚舉兩個左右座標，然後檢查區間`[l,r]`是否滿足最大值為`hmax`且最小值為`hmin`。時間複雜度O($n^3$)
子題二改成枚舉左座標後，枚舉右座標時更新最大最小值，時間複雜度降到O($n^2$)
:::spoiler Python 25% code

n = int(input())
hmin, hmax = map(int, input().split())
heights = list(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i, n):
        min_height = min(heights[i:j+1])
        max_height = max(heights[i:j+1])
        
        if min_height == hmin and max_height == hmax:
            ans += 1

print(ans)

:::
:::spoiler Python 40% code

n = int(input())
hmin, hmax = map(int, input().split())
heights = list(map(int, input().split()))

ans = 0

for i in range(n):
    min_height = heights[i]
    max_height = heights[i]
    
    for j in range(i, n):
        min_height = min(min_height, heights[j])
        max_height = max(max_height, heights[j])
        
        if min_height == hmin and max_height == hmax:
            ans += 1

print(ans)

:::
::: spoiler C++ 40% code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    int hmin, hmax;
    cin >> hmin >> hmax;

    vector<int> heights(n);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
    }

    int count = 0;

    // Iterate over all pairs (i, j)
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            int min_height = *min_element(heights.begin() + i, heights.begin() + j + 1);
            int max_height = *max_element(heights.begin() + i, heights.begin() + j + 1);
            
            if (min_height == hmin && max_height == hmax) {
                count++;
            }
        }
    }

    cout << count << endl;

    return 0;
}

:::
##### AC
1.枚舉右座標，開`flag1`紀錄是否最小值==`hmin`、`flag2`紀錄是否最大值==`hmax`。
2.如果`a[i]`超過`hmax`或小於`hmin`，新的左座標設為i+1，初始左座標設為0。
3.兩個變數紀錄右座標前`hmax`和`hmin`最大出現位置。
4.檢查`flag1`和`flag2`是否成立。如果成立，代表此右座標是合法的。且合法左座標有`min(hmax,hmin)-sl+1`個，把答案加上去即可。
:::spoiler Python AC(0.2s, 16.9MB) code

n = int(input())
hmin, hmax = map(int, input().split())
nums = list(map(int, input().split())) + [hmax + 1]
ans=0
flag1, flag2, sl ,max_hmax,max_hmin=0,0,0,-1,-1
for right in range(n):
    if nums[right]==hmin:flag1=1;max_hmin=right
    if nums[right]==hmax:flag2=1;max_hmax=right
    if nums[right]<hmin or nums[right]>hmax:
        flag1, flag2, sl=0,0,right+1
    if flag1&flag2:ans+=min(max_hmin,max_hmax)-sl+1
print(ans)

:::
:::spoiler C++ AC(0.1s, 1.1MB) code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int hmin, hmax;
    cin >> hmin >> hmax;
    
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    nums.push_back(hmax + 1);  // Add hmax + 1 as the last element

    long long int ans = 0;
    int flag1 = 0, flag2 = 0, sl = 0;
    int max_hmin = -1, max_hmax = -1;

    for (int right = 0; right < n; ++right) {
        if (nums[right] == hmin) {
            flag1 = 1;
            max_hmin = right;
        }
        if (nums[right] == hmax) {
            flag2 = 1;
            max_hmax = right;
        }
        if (nums[right] < hmin || nums[right] > hmax) {
            flag1 = flag2 = 0;
            sl = right + 1;
        }
        if (flag1 && flag2) {
            ans += min(max_hmin, max_hmax) - sl + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

:::

### [第三題](https://zerojudge.tw/ShowProblem?problemid=q376)
#### 考點：前綴和、差分
#### 實作方法
觀察到每次輸入人數(`p`)，左界(`l`)，右界(`r`)，代表警察只要在閉區間`[l,r]`，都可以抓到。=>對於區間的位置每個都加上`p`，再找出最大值即可。右座標只會到$10^6$，故可以直接開長度(m+2)的陣列。
##### 子題一
n<=10 暴力修改陣列，時間複雜度O(`n*m`)
###### 註：ZJ的判題邏輯是memory error就中斷跑下一筆，所以`n,m`太大會導致Python memory error，請將第10筆以後視為TLE。
:::spoiler Python 50% code

n, m = map(int, input().split())

nums = [0] * (m + 1)

for _ in range(n):
    p,l,r=(map(int, input().split()))
    for i in range(l, r + 1):
        nums[i] += p
ans2 = max(nums)
ans1 = nums.index(ans2)
print(ans1, ans2)

:::
:::spoiler C++ 50% code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> nums(m + 1, 0);

    for (int i = 0; i < n; ++i) {
        int p, l, r;
        cin >> p >> l >> r;

        for (int j = l; j <= r; ++j) {
            nums[j] += p;
        }
    }

    int ans2 = *max_element(nums.begin(), nums.end());
    int ans1 = find(nums.begin(), nums.end(), ans2) - nums.begin();

    cout << ans1 << " " << ans2 << endl;

    return 0;
}

:::
##### AC
由於是一直區間修改，最後查詢，故使用差分計算，降低時間複雜度。
由於本題記憶體只有64MB，Python如果直接新開陣列把差分建構成完整陣列為會NA(80%)Memory error(20%)，空間複雜度$2$倍O($m$)，故使用變數計算目前數字，空間複雜度O($m$)。
時間複雜度：讀入資料O($n$)，差分轉前綴和O($m+2$)=O($m$)，總時間複雜度O($n+m$)
:::spoiler Python 80%

from itertools import accumulate
n,m=map(int, input().split())
diff=[0]*(m+2)
for _ in range(n):
    p,l,r=map(int, input().split())
    diff[l]+=p
    diff[r+1]-=p
nums=list(accumulate(diff))
ans2=max(nums)
ans1=nums.index(ans2)
print(ans1,ans2)

:::
:::spoiler Python AC(1.2s, 21.1MB) code

def get_ans(nums,m):
    ans1,ans2=0,nums[0]
    last=nums[0]
    for i in range(1,m+2):
        last+=nums[i]
        if last>ans2:
            ans2=last
            ans1=i
    return (ans1,ans2)
n,m=map(int, input().split())
diff=[0]*(m+2)
for _ in range(n):
    p,l,r=map(int, input().split())
    diff[l]+=p
    diff[r+1]-=p
print(*get_ans(diff,m))

:::
:::spoiler Python AC(0.8s, 21.1MB) code(輸入優化、main)

from sys import stdin

def get_ans(nums, m):
    ans1, ans2 = 0, nums[0]
    last = nums[0]
    for i in range(1, m + 2):
        last += nums[i]
        if last > ans2:
            ans2 = last
            ans1 = i
    return ans1, ans2

def main():
    n, m = map(int, stdin.readline().split())
    diff = [0] * (m + 2)
    for _ in range(n):
        p, l, r = map(int, stdin.readline().split())
        diff[l] += p
        diff[r + 1] -= p
    result = get_ans(diff, m)
    print(*result)

main()

:::
:::spoiler C++ AC(0.5s, 11.8MB) code

#include <bits/stdc++.h>
using namespace std;

vector<long long int> accumulate(const vector<int>& nums, int m) {
    vector<long long int> res(m + 2, 0);
    res[0] = nums[0];
    for (int i = 1; i <= m + 1; ++i) {
        res[i] = res[i - 1] + nums[i];
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> diff(m + 2, 0);

    for (int i = 0; i < n; ++i) {
        long long int p, l, r;
        cin >> p >> l >> r;
        diff[l] += p;
        diff[r + 1] -= p;
    }

    vector<long long int> nums = accumulate(diff, m);
    long long ans2 = *max_element(nums.begin(), nums.end());
    int ans1 = find(nums.begin(), nums.end(), ans2) - nums.begin();

    cout << ans1 << " " << ans2 << endl;
    return 0;
}

:::
:::spoiler C++ AC(0.5s, 4.1MB) code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int diff[m+2]{0};
    while(n--){
        int p,l,r;
        cin>>p>>l>>r;
        diff[l]+=p;
        diff[r+1]-=p;
    }
    long long int prefix=diff[0],ans1=0,ans2=diff[0];
    for (int i=1;i<=m+1;i++){
        prefix+=diff[i];
        if (prefix>ans2){ans2=prefix;ans1=i;}
    }
    cout<<ans1<<' '<<ans2<<endl;
}

:::